REFERENCES

Our work |
Related work |
||||||

Tutorials |
Theory |
Algorithms |
Applications |
Theory |
Algorithms |
Applications |
Websites |

Tutorials

- The Pursuit of Low-dimensional Structures in High-dimensional Data,

Yi Ma, John Wright, Zhouchen Lin, and Allen Y. Yang.

Various versions of these lectures have been offered at ICIP 2010, CVPR 2010, ICIG 2011, VLPR summer school 2011, ADSC summer school 2012, MMDS 2012. -
Sparse Representation and Low-Rank Representation in Computer Vision,

Yi Ma, John Wright, and Allen Y. Yang.

ECCV 2012 Short Course.

Theory

Algorithms

Applications

Related References and Resources by Others

Theory

Algorithms

Applications

Websites

If you would like to list your publications related to this topic on this website, please contact the webmaster Kerui Min.

- Robust Principal Component Analysis?,

Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Journal of the ACM, volume 58, no. 3, May 2011. - Dense
Error Correction via L
^{1}-Minimization,

John Wright, and Yi Ma. IEEE Transactions on Information Theory, volume 56, no. 7, July 2010. - Robust
Principal Component Analysis: Exact Recovery
of Corrupted Low-Rank Matrices via Convex Optimization,

John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. In Proceedings of Neural Information Processing Systems (NIPS), December 2009. - Stable Principal Component Pursuit,

Zihan Zhou, Xiaodong Li, John Wright, Emmanuel Candès, and Yi Ma. In Proceedings of IEEE International Symposium on Information Theory (ISIT), June 2010. - Dense Error Correction for Low-Rank Matrices via Principal Component Pursuit,

Arvind Ganesh, John Wright, Xiaodong Li, Emmanuel Candès, and Yi Ma. In Proceedings of IEEE International Symposium on Information Theory (ISIT), June 2010. - Principal Component Pursuit with Reduced Linear Measurements,

Arvind Ganesh, Kerui Min, John Wright, and Yi Ma. submitted to International Symposium on Information Theory, 2012. - Compressive Principal Component Pursuit,

John Wright, Arvind Ganesh, Kerui Min, and Yi Ma. submitted to International Symposium on Information Theory, 2012.

Algorithms

- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices,

Zhouchen Lin, Minming Chen, and Yi Ma. UIUC Technical Report UILU-ENG-09-2214, October 2010.

[arXiv version] - Fast
Convex Optimization Algorithms for Exact
Recovery of a Corrupted Low-Rank Matrix,

Zhouchen Lin, Arvind Ganesh, John Wright, Leqin Wu, Minming Chen, and Yi Ma. UIUC Technical Report UILU-ENG-09-2214, July 2009. - Fast
Algorithms for Recovering a Corrupted Low-Rank
Matrix,

Arvind Ganesh, Zhouchen Lin, John Wright, Leqin Wu, Minming Chen, and Yi Ma. In Proceedings of International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), December 2009.

Applications

- RASL: Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images,

Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma. Submitted to IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), July 2010.

[Project website with sample code and data] [Conference version presented at CVPR 2010] - Decomposing Background Topics from Keywords by Principal Component Pursuit,

Kerui Min, Zhengdong Zhang, John Wright, and Yi Ma. In Proceedings of ACM International Conference on Information and Knowledge Management (CIKM), October 2010. - Image Tag Refinement Towards Low-Rank, Content-Tag Prior and Error Sparsity,

Guangyu Zhu, Shuicheng Yan, and Yi Ma. In Proceedings of ACM Multimedia, October 2010. - TILT: Transform Invariant Low-rank Textures,

Zhengdong Zhang, Arvind Ganesh, Xiao Liang, and Yi Ma. Submitted to International Journal of Computer Vision (IJCV), December 2010.

[Project website with sample code and data] [Conference version presented at ACCV 2010] [arXiv version] - Convex Optimization Based Low-Rank Matrix Completion and Recovery for Photometric Stereo and Factor Classification,

Lun Wu, Arvind Ganesh, Boxin Shi, Yasuyuki Matsushita, Yongtian Wang, and Yi Ma. Submitted to IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), August 2011.

[Project website] [Conference version presented at ACCV 2010] - Camera Calibration with Lens Distortion from Low-rank Textures,

Zhengdong Zhang, Yasuyuki Matsushita, and Yi Ma. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2011. - Face Recovery in Conference Video Streaming using Robust Principal Component Analysis,

Wai-tian Tan, Gene Cheung, and Yi Ma. To appear in Proceedings of IEEE International Conference on Image Processing (ICIP), September 2011. - Unwrapping Low-rank Textures on Generalized Cylindrical Surfaces,

Zhengdong Zhang, Xiao Liang, and Yi Ma. To appear in Proceedings of International Conference on Computer Vision (ICCV), November 2011. - Holistic 3D Reconstruction of Urban Structures from Low-Rank Textures,

Hossein Mobahi, Zihan Zhou, Allen Yang, and Yi Ma. To appear in 3rd International IEEE Workshop on 3D Representation and Recognition (3dRR-11), November 2011. - Repairing Sparse Low-rank Texture,

Xiao Liang, Xiang Ren, Zhengdong Zhang, and Yi Ma, European Conference on Computer Vision (ECCV), October 2012. - Robust and Practical Face Recognition via Structured Sparsity,

Kui Jia, Tsung-Han Chan, and Yi Ma, European Conference on Computer Vision (ECCV), October 2012.

Related References and Resources by Others

Theory

- Guaranteed
Minimum Rank Solutions to Linear Matrix Equations via
Nuclear Norm Minimization,

B. Recht, M. Fazel, and P. A. Parrilo. To appear in SIAM Review. - Null
Space Conditions and Thresholds for Rank Minimization,

B. Recht, W. Xu, and B. Hassibi. To appear in Mathematical Programming, 2010. - Exact
Matrix Completion via Convex Optimization,

E. J. Candès, and B. Recht. Foundations of Computational Mathematics, 2009. - The
Power of Convex Relaxation: Near-Optimal Matrix Completion,

E. J. Candès, and T. Tao. IEEE Transactions on Information Theory, 2009. - Matrix
Completion with Noise,

E. J. Candès, and Y. Plan. Proceedings of the IEEE, 2009. - Rank-Sparsity
Incoherence for Matrix Decomposition,

V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. SIAM Journal on Optimization, volume 21, issue 2, 2011. - Matrix
Completion from a Few Entries,

R. H. Keshavan, A. Montanari, and S. Oh. Preprint, 2009. - Matrix
Completion from Noisy Entries,

R. H. Keshavan, A. Montanari, and S. Oh. Preprint, 2009. - Uniqueness of Low-Rank Matrix Completion by Rigidity Theory,

A. Singer, and M. Cucuringu. SIAM Journal on Matrix Analysis and Applications, 2010. - Recovering Low-Rank Matrices from Few Coefficients in Any Basis,

D. Gross. IEEE Transactions on Information Theory, volume 57, issue 3, March 2011. - A Unified Framework for High-Dimensional Analysis of M-estimators with Decomposable Regularizers,

S. Negahban, P. Ravikumar, M. Wainwright, and B. Yu. In Proceedings of NIPS, December 2009. - Matrix Completion from Power-Law Distributed Samples,

R. Meka, P. Jain, and I. S. Dhillon. In Proceedings of NIPS, December 2009. - Tight Oracle Bounds for Low-Rank Matrix Recovery from a Minimal Number of Random Measurements,

E. J. Candès, and Y. Plan. IEEE Transactions on Information Theory, volume 57, issue 4, 2011. - Information Theoretic Bounds for Low-Rank Matrix Completion,

S. Vishwanath. In Proceedings of ISIT, June 2010. - Regularization for Matrix Completion,

R. H. Keshavan, and A. Montanari. In Proceedings of ISIT, June 2010. - New Restricted Isometry Results for Noisy Low-rank Recovery,

K. Mohan and M. Fazel. In Proceedings of ISIT, June 2010. - A Nullspace Analysis of the Nuclear Norm Heuristic for Rank Minimization,

K. Dvijotham and M. Fazel. In Proceedings of ICASSP, 2010. - Robust Matrix Decomposition with Sparse Corruptions,

D. Hsu, S. M. Kakade, and T. Zhang. To appear in IEEE Transactions on Information Theory, 2011. - Robust Low-Rank Subspace Segmentation with Semidefinite Guarantees,

Y. Ni, J. Sun, X. Yuan, S. Yan, and L-F.Cheong. Preprint, 2010. - Robust Recovery of Subspace Structures by Low-Rank Representation,

G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma. Preprint, 2010. - Robust PCA via Outlier Pursuit,

H. Xu, C. Caramanis, and S. Sanghavi. In Proceedings of NIPS, 2010. - Latent Variable Graphical Model Selection via Convex Optimization,

V. Chandrasekaran, P. A. Parrilo, and A. S. Willsky. Preprint, 2010. - The Convex Geometry of Linear Inverse Problems,

V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky. Preprint, 2010. - Two Proposals for Robust PCA using Semidefinite Programming,

M. McCoy, and J. Tropp. Preprint, 2010. - Robust Matrix Completion with Corrupted Columns,

Y. Chen, H. Xu, C. Caramanis, and S. Sanghavi. Preprint, 2011. - Rank, Trace-Norm and Max-Norm,

N. Srebro, and A. Shraibman. In Proceedings of COLT, June 2005. - Noisy Matrix Decomposition via Convex Relaxation: Optimal Rates in High Dimensions,

A. Agarwal, S. Negahban, and M. J. Wainwright. Preprint, Feb 2011. - Sparse Bayesian Methods for Low-Rank Matrix Estimation,

S. D. Babacan, M. Luessi, R. Molina, and A. K. Katsaggelos. Preprint, Feb 2011. - Concentration-Based Guarantees for Low-Rank Matrix Reconstruction,

R. Foygel, and N. Srebro. Preprint, Feb 2011. - A Simple Algorithm for Nuclear Norm Regularized Problems,

M. Jaggi, and M. Sulovsky. In Procedings of ICML, June 2010. - Divide-and-Conquer Matrix Factorization,

L. Mackey, A. Talwalker, and M. I. Jordan. To appear in Proceedings of NIPS, 2011. - Simple Bounds for Low-complexity Model Reconstruction,

E. Candès, and B. Recht. Preprint, March 2011. - The Stability of Low-Rank Matrix Reconstruction: a Constrained Singular Value View,

G. Tang, and A. Nehorai. Preprint, June 2010. - Lower Bounds on the Mean-Squared Error of Low-Rank Matrix Reconstruction,

G. Tang, and A. Nehorai. To appear in IEEE Transactions on Signal Processing, 2011. - SpaRCS: Recovering Low-Rank and Sparse Matrices from Compressive Measurements,

A. Waters, A. Sankaranarayanan, and R. Baraniuk. To appear in Proceedings of NIPS, 2011. - PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming. ,

E. J. Candes, T. Strohmer and V. Voroninski, to appear in Communications on Pure and Applied Mathematics, 2011 - A geometric analysis of subspace clustering with outliers,

M. Soltanolkotabi and E. J. Candes., to appear in Annals of Statistics, 2011 - Towards a mathematical theory of super-resolution,

E. J. Candes and C. Fernandez-Granda., to appear in Communications on Pure and Applied Mathematics, 2012 -
Exact Recovery of Sparsely-Used Dictionaries,

D. A. Spielman, H. Wang, and J. Wright, In JMLR, 2012 -
Computing a Nonnegative Matrix Factorization -- Provably,

S. Arora, R. Ge, R. Kannan, A. Moitra, In STOC, 2012 - Sharp recovery bounds for convex deconvolution, with applications,

M. B. McCoy and J. A. Tropp., preprint, 2012 - Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting,

J. Saunderson, V. Chandrasekaran, P. A. Parrilo, A. S. Willsky, preprint, 2012

Algorithms

- A
Singular Value Thresholding Algorithm for Matrix Completion,

J. -F. Cai, E. J. Candès, and Z. Shen. Preprint, 2008. - A
Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse
Problems,

A. Beck, and M. Teboulle. SIAM Journal on Imaging Sciences, vol. 2, no. 1, March 2009. - An
Accelerated Proximal Gradient Algorithm for Nuclear Norm Regularized
Least Squares Problems,

K. -C. Toh, and S. Yun. Preprint, 2009. - On
Accelerated Proximal Gradient Methods for Convex-Concave Optimization,

P. Tseng. Preprint, 2008. - A
Method for Solving a Convex Programming Problem with Convergence Rate 1
/ k
^{2},

Yu. Nesterov. Soviet Mathematics Doklady, 1983. - Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization,

S. Ma, D. Goldfarb, and L. Chen. Preprint, 2009. - Convergence of Fixed Point Continuation Algorithms for Matrix Rank Minimization,

D. Goldfarb, and S. Ma. Preprint, 2009. - ADMiRA: Atomic Decomposition for Minimum Rank Approximation,

K. Lee, and Y. Bresler. Preprint, 2009. - SET: An Algorithm for Consistent Matrix Completion,

W. Dai, and O. Milenkovic. Preprint, 2009. - Row by Row Methods for Semidefinite Programming,

Z. Wen, D. Goldfarb, S. Ma, and K. Scheinberg. Preprint, 2009. - Spectral Regularization Algorithms for Learning Large Incomplete Matrices,

R. Mazumder, T. Hastie, and R. Tibshirani. Preprint, 2009. - Sparse and Low-Rank Matrix Decomposition via Alternating Direction Methods,

X. Yuan, and J. Yang. Preprint, 2009. - Interior-point method for Nuclear Norm Approximation with Application to System Identification,

Z. Liu and L. Vandenberghe. SIAM Journal on Matrix Analysis and Applications, 31(3), 2009. - Rank-Constrained Solutions to Linear Matrix Equations using Power Factorization,

J. Haldar, and D. Hernando. IEEE Signal Processing Letters, 16, 2009. - Low Rank Matrix Approximation in Linear Time,

S. Har-Peled. Preprint, 2006. - Guaranteed Rank Minimization via Singular Value Projection,

R. Meka, P. Jain, and I. S. Dhillon. Preprint, 2009. - Rank Minimization via Online Learning,

P. Jain, R. Meka, C. Caramanis, and I. S. Dhillon. In Proceedings of ICML, July 2008. - Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations,

A. Frieze, R. Kannan and S. Vempala. In Proceedings of FOCS, 1998. - A Fast and Efficient Algorithm for Low-Rank Approximation of a Matrix,

N. H. Nguyen, T. T. Do, and T. D. Tran. In Proceedings of STOC, January 2009. - Solving a Low-Rank Factorization Model for Matrix Completion by a Non-linear Successive Over-Relaxation Algorithm,

Z. Wen, W. Yin, and Y. Zhang. Preprint, March 2010. - Reweighted Nuclear Norm Minimization with Application to System Identification,

K. Mohan and M. Fazel. In Proceedings of ACC, July 2010. - A Fast Augmented Lagrangian Algorithm for Learning Low-Rank Matrices,

R. Tomioka, T. Suzuki, M. Sugiyama, and H. Kashima. In Proceedings of ICML, June 2010. - IMP: A Message-Passing Algorithm for Matrix Completion,

B. -H. Kim, A. Yedla, and H. D. Pfister. Preprint, 2010. - Fast Singular Value Thresholding without Singular Value Decomposition,

J. -F. Cai, and S. Osher. UCLA CAM Report 10-24, 2010. - Online Identification and Tracking of Subspaces from Highly Incomplete Information,

L. Balzano, R. Nowak, and B. Recht. Preprint, 2010. - Real-time Robust Principal Components' Pursuit,

C. Qiu, and N. Vaswani. In Proceedings of Allerton, September 2010. - Templates for Convex Cone Problems with Applications to Sparse Signal Recovery,

S. Becker, E. J. Candès, and M. Grant. Preprint, September 2010. - Iterative Reweighted Least Squares for Matrix Rank Minimization,

K. Mohan, and M. Fazel. In Proceedings of Allerton, September 2010. - Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions,

D. Goldfarb, S. Ma, and K. Scheinberg. Preprint, 2010. - Practical Large-Scale Optimization for Max-Norm Regularization,

J. Lee, B. Recht, R. Salakhutdinov, N. Srebro, and J. Tropp. In Proceedings of NIPS, 2010. - Maximum Margin Matrix Factorizations,

N. Srebro, J. Rennie, and T. Jaakkola. In Proceedings of NIPS, 2004. - SRF: Matrix Completion based on Smoothed Rank Function,

H. Ghasemi, M. Malek-Mohammadi, M. Babaie-Zadeh, and C. Jutten. To appear in Proceedings of ICASSP, 2011. - Parallel Stochastic Gradient Algorithms for Large-Scale Matrix Completion,

B. Recht, and C. Re. Preprint, 2011. - An Implementable Proximal Point Algorithmic Framework for Nuclear Norm Minimization,

Y-J. Liu, D. Sun, and K-C. Toh. To appear in Mathematical Programming, December 2010. - Exactly Recovering Low-Rank Matrix in Linear Time via l1 Filter,

R. Liu, Z. Lin, and Z. Shu. Preprint, August 2011. - Accelerated Low-rank Visual Recovery by Random Projection,

Y. Mu, J. Dong, X. Yuan, and S. Yan. In Proceedings of CVPR, June 2011. - Large-Scale Convex Minimization with a Low-Rank Constraint,

S. Shalev-Shwartz, A. Gonen, and O. Shamir. In Proceedings of ICML, 2011. - Fast First-Order Methods for Stable Principal Component Pursuit,

N. Aybat, D. Goldfarb, and G. Iyengar. Preprint, 2011. - Fast global convergence of gradient methods for high-dimensional statistical recovery,

A. Agarwal, S. Negahban, and M. Wainwright. Preprint, 2011. - Convergence rates of Inexact Proximal-Gradient Methods for Convex Optimization,

M. Schmidt, N. L. Roux, and F. Bach. Preprint, September 2011. - Fast Incremental Method for Matrix Completion: an Application to Trajectory Correction,

R. S. Cabral, J. P. Costeira, F. De la Torre and A. Bernardino. IEEE Conference on Image Processing (ICIP), 2011. - GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case,

T. Zhou, and D. Tao. In Proceedings of ICML, 2011. - Low-rank optimization with trace norm penalty,

B. Mishra, G. Meyer, F. Bach, R. Sepulchre. preprint, 2011. - RTRMC: A Riemannian trust-region method for low-rank matrix completion,

N. Boumal and P.-A. Absil. In Proceedings of NIPS, 2012. - Solving Principal Component Pursuit in Linear Time via l_1 Filtering,

R. Liu, Z. Lin, S. Wei, Z. Su, preprint, 2011. - Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures,

X. Ren, Z. Lin, preprint, 2012. - Normalized Iterative Hard Thresholding for Matrix Completion,

J. Tanner, K. Wei, preprint, 2012.

Applications

- Collaborative Spectrum Sensing from Sparse Observations
using Matrix Completion for Cognitive Radio Networks,

J. Meng, W. Yin, E. Houssain, and Z. Han. In Proceedings of ICASSP, 2010. - Semidefinite Programming Methods for System Realization and Identification,

Z. Liu, and L. Vandenberghe. In Proceedings of CDC, 2009. - Robust Video Denoising using Low Rank Matrix Completion,

H. Ji, C. Liu, Z. Shen, and Y. Xu. In Proceedings of CVPR, June 2010. - Fast Maximum Margin Matrix Factorization for Collaborative Prediction,

J. Rennie, and N. Srebro. In Proceedings of ICML, August 2005. - Application of Trace-Norm and Low-Rank Matrix Decomposition for Computational Anatomy,

N. Batmanghelich, A. Gooya, S. Kanterakis, B. Taskar, and C. Davatzikos. In Proceedings of MMBIA (CVPR Workshop), June 2010. - Ultrasound Tomography Calibration Using Structured Matrix Completion,

A. Karbasi, S. Oh, R. Parhizkar, and M. Vetterli. In Proceedings of International Congress of Acoustics, August 2010. - Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm,

R. Salakhutdinov, and N. Srebro. In Proceedings of NIPS, 2010. - Imaging via Three-dimensional Compressive Sampling (3DCS),

X. Shu, and N. Ahuja. To appear in Proceedings of ICCV, 2011. - Robust Subspace Segmentation by Low-Rank Representation,

G. Liu, Z. Lin, and Y. Yu. In Proceedings of ICML, June 2010. - Robust principal component analysis-based four-dimensional computed tomography,

H. Gao, J. -F. Cai, Z. Shen, and H. Zhao. Physics in Medicine and Biology, volume 56, no. 11, 2011. - Latent Low-Rank Representation for Subspace Segmentation and Feature Extraction,

G. Liu, and S. Yan. To appear in Proceedings of ICCV, November 2011. - Multi-task Low-rank Affinity Pursuit for Image Segmentation,

B. Cheng, G. Liu, J. Wang, Z. Huang, and S. Yan. To appear in Proceedings of ICCV, November 2011. - Finding Dense Clusters via "Low Rank + Sparse" Decomposition,

S. Oymak, and B. Hassibi. Preprint, April 2011. - Clustering Partially Observed Graphs via Convex Optimization,

A. Jalali, Y. Chen, S. Sanghavi, and H. Xu. In Proceedings of ICML, 2011. - Structure Analysis of Network Traffic Matrix based on Relaxed Principal Component Pursuit,

Z. Wang, K. Hu, K. Xu, and B. Yin. Preprint, April 2011. - Sparse Online Low-Rank Projection and Outlier Rejection (SOLO) for 3-D Rigid-Body Motion Registration,

C. Slaughter, A. Yang, J. Bagwell, C. Checkles, L. Sentis, and S. Vishwanath. Preprint, September 2011. - Matrix Completion for Multi-label Image Classification,

R. S. Cabral, F. De la Torre, J. P. Costeira and A. Bernardino. Advances in Neural Information Processing Systems (NIPS), 2011. - Robust Principal Component Analysis
for Background Subtraction: Systematic Evaluation and Comparative
Analysis,

C. Guyon, T. Bouwmans, E. Zahzah. INTECH, Principal Component Analysis, Book 1, Chapter 12, page 223-238, March 2012. - Non-Negative Low Rank and Sparse Graph for Semi-Supervised Learning,

L. Zhuang, H. Gao, Z. Lin, Y. Ma, X. Zhang, N. Yu. In Proceedings of CVPR, 2012. - Singing-Voice Separation from Monaural Recordings using Robust Principal Component Analysis,

P. Huang, S. D. Chen, P. Smaragdis, and M. H. Johnson, In ICASSP, 2012.

Websites

- Singular Value Thresholding
- Compressed Sensing Resources
- CVX: Matlab package for general convex optimization
- OptSpace: A Matrix Completion Algorithm
- FPCA: Fixed Point Continuation with Approximate SVD
- NNLS: Nuclear Norm Regularized Linear Least Squares
- Nuclear Norm Approximation - CVXOPT
- GROUSE: Grassmann Rank-One Update Subspace Estimation
- TFOCS: Templates for First-Order Conic Solvers
- DFC: Divide-and-Conquer Matrix Factorization
- List of various sparse and low-rank recovery algorithms

If you would like to list your publications related to this topic on this website, please contact the webmaster Kerui Min.