On Approximation Guarantees for Greedy Low Rank Optimization

Rajiv Khanna, Ethan R. Elenberg, Alexandros G. Dimakis, Sahand Negahban

Type: Preprint

Publication Date: 2017-01-01

Citations: 5

DOI: https://doi.org/10.48550/arxiv.1703.02721

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees	2015	Yudong Chen Martin J. Wainwright
+	Local Search Algorithms for Rank-Constrained Convex Optimization	2021	Kyriakos Axiotis Maxim Sviridenko
+	Large-Scale Convex Minimization with a Low-Rank Constraint	2011	Shai Shalev‐Shwartz Alon Gonen Ohad Shamir
+	Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms	2019	Thomas Zhang
+ PDF Chat	Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds	2014	Rafi Witten Emmanuel J. Candès
+	Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions	2023	Dimitris Bertsimas Ryan Cory-Wright Sean Lo Jean Pauphilet
+	Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage	2017	Alp Yurtsever Madeleine Udell Joel A. Tropp Volkan Cevher
+	Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage	2017	Alp Yurtsever Madeleine Udell Joel A. Tropp Volkan Cevher
+	Local Search Algorithms for Rank-Constrained Convex Optimization	2021	Kyriakos Axiotis Maxim Sviridenko
+	Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization	2019	Yuxin Chen Yuejie Chi Jianqing Fan Cong Ma Yuling Yan
+	Fast Low-Rank Matrix Estimation without the Condition Number	2017	Mohammadreza Soltani Chinmay Hegde
+	Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization	2020	Yuxin Chen Yuejie Chi Jianqing Fan Cong Ma Yuling Yan
+	Towards a Zero-One Law for Entrywise Low Rank Approximation.	2018	Zhao Song David P. Woodruff Peilin Zhong
+	Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle	2020	Lijun Ding Yuqian Zhang Yudong Chen
+	On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness	2020	Alfredo Torrico Mohit Singh Sebastian Pokutta
+	Low Rank Approximation	2011	Ivan Markovsky
+	On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness.	2020	Alfredo Torrico Mohit Singh Sebastian Pokutta
+	Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach	2021	Dimitris Bertsimas Ryan Cory-Wright Nicholas A. G. Johnson
+ PDF Chat	Guaranteed Matrix Completion via Nonconvex Factorization	2015	Ruoyu Sun Zhi‐Quan Luo
+ PDF Chat	Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling	2023	Xumei Xi Christina Lee Yu Yudong Chen

Works That Cite This (5)

Action	Title	Year	Authors
+	Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms	2019	Thomas Zhang
+	Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning	2020	Zhiyuan Li Yuping Luo Kaifeng Lyu
+ PDF Chat	Targeted Sampling from Massive Block Model Graphs with Personalized PageRank	2019	Fan Chen Yini Zhang Karl Rohe
+	Robust Principal Component Analysis with Non-Sparse Errors	2019	Jushan Bai Junlong Feng
+ PDF Chat	Subspace Selection via DR-Submodular Maximization on Lattices	2019	So Nakashima Takanori Maehara

Works Cited by This (16)

Action	Title	Year	Authors
+	A Simple Algorithm for Nuclear Norm Regularized Problems	2010	Martin Jaggi Marek Sulovský
+ PDF Chat	Estimation of (near) low-rank matrices with noise and high-dimensional scaling	2011	Sahand Negahban Martin J. Wainwright
+	Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima	2015	Po‐Ling Loh Martin J. Wainwright
+	A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers	2012	Sahand Negahban Pradeep Ravikumar Martin J. Wainwright Bin Yu
+	On Iterative Hard Thresholding Methods for High-dimensional M-Estimation	2014	Prateek Jain Ambuj Tewari Purushottam Kar
+	Large-Scale Convex Minimization with a Low-Rank Constraint	2011	Shai Shalev‐Shwartz Alon Gonen Ohad Shamir
+	Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization	2013	Martin Jaggi
+ PDF Chat	Forward–Backward Greedy Algorithms for Atomic Norm Regularization	2015	Nikhil Rao Parikshit Shah Stephen J. Wright
+ PDF Chat	Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion	2015	Zheng Wang Ming‐Jun Lai Zhaosong Lu Wei Fan Hasan Davulcu Jieping Ye
+ PDF Chat	Approximation and learning by greedy algorithms	2008	Andrew R. Barron Albert Cohen Wolfgang Dahmen Ronald DeVore