A Sufficient Condition for Low-Rank Recovery via Iterative Hard Thresholding Pursuit

Abstract:

In this pape, we propose a matrix Iterative Hard thresholding pursuit algorithm for low-rank minimization that extends Foucart's Hard Thresholding Pursuit (HTP) algorithm from the sparse vector to the low-rank matrix case. The performance guarantee is given in terms of the rank-restricted isometry property and a low-rank solotion is presented. The numerical experiments empirically demonstrate that, although the affine constraints does not satisfy the restricted isometry property in matrix completion, our algorithm also recovers the low-rank matrix from a number of uniformly sampled entries and is more efficient compared with SVT and ADMiRA.

• Periodical: Applied Mechanics and Materials (Volumes 644-650)
• Pages: 2378-2381
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.644-650.2378
• Online since: September 2014
• Authors: Li Cui*, Lu Liu, Xue Zhi Huang
• Keywords: Hard Thresholding Pursuit, Low-Rank Minimization, Matrix Completion, Restricted Isometry Property

References

[1] Mesbahi M, Papavassilopoulos G. On the rank minimization problem over a positive semidefinite linear matrix inequality. IEEE Transactions on Automatic Control, 1997, 42(2): 239—243.

DOI: 10.1109/9.554402

[2] Shapiro A. Weighted minimum trace factor analysis. Psychometrika, 1982, 47(3): 243-264.

DOI: 10.1007/bf02294158

[3] Evgeniou A, Pontil M. Multi-task feature learning. Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference, MIT Press, 2007, 19: 41.

DOI: 10.7551/mitpress/7503.003.0010

[4] Recht B, Fazel M, Parrilo P. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 2010, 52(3): 471—501.

DOI: 10.1137/070697835

[5] Lee K, Bresler Y. Guaranteed minimum rank approximation from linear observations by nuclear norm minimization with an ellipsoidal constraint. arXiv preprint arXiv: 0903. 4742, (2009).

[6] Lee K, Bresler Y. Admira: Atomic decomposition for minimum rank approximation. IEEE Transactions on Information Theory, 2010, 56(9): 4402-4416.

DOI: 10.1109/tit.2010.2054251

[7] Needell D, Tropp J. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 2009, 26(3): 301-321.

DOI: 10.1016/j.acha.2008.07.002

[8] Goldfarb D, Ma S. Convergence of fixed-point continuation algorithms for matrix rank minimization. Foundations of Computational Mathematics, 2011, 11(2): 183-210.

DOI: 10.1007/s10208-011-9084-6

[9] Meka R, Jain P, Dhillon I. Guaranteed rank minimization via singular value projection. arXiv preprint arXiv: 0909. 5457, (2009).

[10] Blumensath T, Davies M E. Normalized iterative hard thresholding: Guaranteed stability and performance. IEEE Journal of Selected Topics in SignalProcessing, 4(2): 298-309.

DOI: 10.1109/jstsp.2010.2042411

[11] Foucart S. Hard thresholding pursuit: an algorithm for compressive sensing. SIAM Journal on Numerical Analysis, 2011, 49(6): 2543-2563.

DOI: 10.1137/100806278

[12] R. ~Larsen, ``Propack-software for large and sparse svd calculations, http: /sun. stanford. edu/~rmunk/PROPACK.

[13] J. ~Cai, E. ~Candes, and Z. ~Shen, ``A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, vol. 20, no. 4, pp.1956-1982, (2010).

DOI: 10.1137/080738970