×

zbMATH — the first resource for mathematics

A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery. (English) Zbl 1335.15031
Summary: In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let \(A, B \in \mathbb{R}^{m \times n}\) be given matrices, and let \(f : \mathbb{R}_+ \to \mathbb{R}_+\) be a concave function satisfying \(f(0) = 0\). Then, we have \[ \sum_{i = 1}^{\min \{m, n \}} | f(\sigma_i(A)) - f(\sigma_i(B)) | \leq \sum_{i = 1}^{\min \{m, n \}} f(\sigma_i(A - B)), \] where \(\sigma_i(\cdot)\) denotes the \(i\)-th largest singular value of a matrix. This answers an open question that is of interest to both the compressive sensing and linear algebra communities. In particular, by taking \(f(\cdot) = (\cdot)^p\) for any \(p \in(0, 1]\), we obtain a perturbation inequality for the so-called Schatten \(p\)-quasi-norm, which allows us to confirm the validity of a number of previously conjectured conditions for the recovery of low-rank matrices via the popular Schatten \(p\)-quasi-norm heuristic. We believe that our result will find further applications, especially in the study of low-rank matrix recovery.

MSC:
15A45 Miscellaneous inequalities involving matrices
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ando, T., Comparison of norms \(||| f(A) - f(B) |||\) and \(||| f(| A - B |) |||\), Math. Z., 197, 3, 403-409, (1988) · Zbl 0618.47007
[2] Audenaert, K. M.R., A generalisation of Mirsky’s singular value inequalities, (2014), Manuscript, available at
[3] Audenaert, K. M.R.; Kittaneh, F., Problems and conjectures in matrix and operator inequalities, (2012), Manuscript, available at
[4] Bhatia, R., Matrix analysis, Graduate Texts in Mathematics, vol. 169, (1997), Springer-Verlag, New York, Inc. New York
[5] Bourin, J.-C.; Uchiyama, M., A matrix subadditivity inequality for \(f(A + B)\) and \(f(A) + f(B)\), Linear Algebra Appl., 423, 2-3, 512-518, (2007) · Zbl 1123.15013
[6] Cai, T. T.; Zhang, A., Sharp RIP bound for sparse signal and low-rank matrix recovery, Appl. Comput. Harmon. Anal., 35, 1, 74-93, (2013) · Zbl 1310.94021
[7] Candès, E.; Recht, B., Simple bounds for recovering low-complexity models, Math. Program., Ser. A, 141, 1-2, 577-589, (2013) · Zbl 1278.15038
[8] Candès, E. J.; Plan, Y., Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Trans. Inform. Theory, 57, 4, 2342-2359, (2011) · Zbl 1366.90160
[9] Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 12, 4203-4215, (2005) · Zbl 1264.94121
[10] Chandrasekaran, V.; Recht, B.; Parrilo, P. A.; Willsky, A. S., The convex geometry of linear inverse problems, Found. Comput. Math., 12, 6, 805-849, (2012) · Zbl 1280.52008
[11] Chartrand, R.; Staneva, V., Restricted isometry properties and nonconvex compressive sensing, Inverse Probl., 24, 3, 035020, (2008) · Zbl 1143.94004
[12] Chen, P.; Suter, D., Recovering the missing components in a large noisy low-rank matrix: application to SFM, IEEE Trans. Pattern Anal. Mach. Intell., 26, 8, 1051-1063, (2004)
[13] Fazel, M.; Hindi, H.; Boyd, S. P., A rank minimization heuristic with application to minimum order system approximation, (Proceedings of the 2001 American Control Conference, (2001)), 4734-4739
[14] Fiedler, M., Bounds for the determinant of the sum of Hermitian matrices, Proc. Amer. Math. Soc., 30, 1, 27-31, (1971) · Zbl 0277.15010
[15] Fulton, W., Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bull. Amer. Math. Soc. (N.S.), 37, 3, 209-249, (2000) · Zbl 0994.15021
[16] Ge, D.; Jiang, X.; Ye, Y., A note on the complexity of \(L_p\) minimization, Math. Program., Ser. B, 129, 2, 285-299, (2011) · Zbl 1226.90076
[17] Gribonval, R.; Nielsen, M., Sparse representations in unions of bases, IEEE Trans. Inform. Theory, 49, 12, 3320-3325, (2003) · Zbl 1286.94032
[18] Hu, Y.; Zhang, D.; Ye, J.; Li, X.; He, X., Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Trans. Pattern Anal. Mach. Intell., 35, 9, 2117-2130, (2013)
[19] Javanmard, A.; Montanari, A., Localization from incomplete noisy distance measurements, Found. Comput. Math., 13, 3, 297-345, (2013) · Zbl 1269.05098
[20] Ji, H.; Liu, C.; Shen, Z.; Xu, Y., Robust video denoising using low rank matrix completion, (Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2010, (2010)), 1791-1798
[21] Ji, S.; Sze, K.-F.; Zhou, Z.; So, A. M.-C.; Ye, Y., Beyond convex relaxation: a polynomial-time non-convex optimization approach to network localization, (Proceedings of the 32nd IEEE International Conference on Computer Communications, INFOCOM 2013, (2013)), 2499-2507
[22] Juditsky, A.; Karzan, F. K.; Nemirovski, A., On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures, Linear Algebra Appl., 441, 124-151, (2014) · Zbl 1332.94044
[23] Koltchinskii, V.; Lounici, K.; Tsybakov, A. B., Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Ann. Statist., 39, 5, 2302-2329, (2011) · Zbl 1231.62097
[24] Kong, L.; Xiu, N., Exact low-rank matrix recovery via nonconvex Schatten p-minimization, Asia-Pac. J. Oper. Res., 30, 3, (2013) · Zbl 1273.90257
[25] M.-J. Lai, S. Li, L.Y. Liu, H. Wang, Two results on the Schatten p-quasi-norm minimization for low-rank matrix recovery, Manuscript 2012.
[26] Lai, M.-J.; Xu, Y.; Yin, W., Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization, SIAM J. Numer. Anal., 51, 2, 927-957, (2013) · Zbl 1268.49038
[27] Lewis, A. S.; Sendov, H. S., Nonsmooth analysis of singular values. part II: applications, Set-Valued Anal., 13, 3, 243-264, (2005) · Zbl 1129.49026
[28] Marjanovic, G.; Solo, V., On \(l_q\) optimization and matrix completion, IEEE Trans. Signal Process., 60, 11, 5714-5724, (2012) · Zbl 1393.94353
[29] Mirsky, L., Symmetric gauge functions and unitarily invariant norms, Q. J. Math., 11, 1, 50-59, (1960) · Zbl 0105.01101
[30] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 2, 227-234, (1995) · Zbl 0827.68054
[31] Negahban, S.; Wainwright, M. J., Estimation of (near) low-rank matrices with noise and high-dimensional scaling, Ann. Statist., 39, 2, 1069-1097, (2011) · Zbl 1216.62090
[32] Nie, F.; Huang, H.; Ding, C., Low-rank matrix recovery via efficient Schatten p-norm minimization, (Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI-12, (2012)), 655-661
[33] Oymak, S.; Mohan, K.; Fazel, M.; Hassibi, B., A simplified approach to recovery conditions for low rank matrices, (Proceedings of the 2011 IEEE International Symposium on Information Theory, ISIT 2011, (2011)), 2318-2322
[34] Pan, Z.; Zhang, C., Relaxed sparse eigenvalue conditions for sparse estimation via non-convex regularized regression, Pattern Recognit., 48, 1, 231-243, (2015) · Zbl 06805405
[35] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501, (2010) · Zbl 1198.90321
[36] Recht, B.; Xu, W.; Hassibi, B., Null space conditions and thresholds for rank minimization, Math. Program., Ser. B, 127, 1, 175-202, (2011) · Zbl 1211.90172
[37] Royden, H. L., Real analysis, (1988), Macmillan Publishing Company New York · Zbl 0704.26006
[38] Ruszczyński, A., Nonlinear optimization, (2006), Princeton University Press Princeton, New Jersey · Zbl 1108.90001
[39] Stewart, G. W.; Sun, J., Matrix perturbation theory, (1990), Academic Press Boston
[40] Strohmer, T., Measure what should be measured: progress and challenges in compressive sensing, IEEE Signal Process. Lett., 19, 12, 887-893, (2012)
[41] Thompson, R. C.; Freede, L. J., On the eigenvalues of sums of Hermitian matrices, Linear Algebra Appl., 4, 4, 369-376, (1971) · Zbl 0228.15005
[42] Wang, M.; Xu, W.; Tang, A., On the performance of sparse recovery via \(\ell_p\)-minimization (\(0 \leq p \leq 1\)), IEEE Trans. Inform. Theory, 57, 11, 7255-7278, (2011) · Zbl 1365.65177
[43] Wen, J.; Li, D.; Zhu, F., Stable recovery of sparse signals via \(l_p\)-minimization, Appl. Comput. Harmon. Anal., 38, 1, 161-176, (2015) · Zbl 1345.94020
[44] Wu, R.; Chen, D.-R., The improved bounds of restricted isometry constant for recovery via \(\ell_p\)-minimization, IEEE Trans. Inform. Theory, 59, 9, 6142-6147, (2013) · Zbl 1364.94177
[45] Zhang, M.; Huang, Z.-H.; Zhang, Y., Restricted p-isometry properties of nonconvex matrix recovery, IEEE Trans. Inform. Theory, 59, 7, 4316-4323, (2013) · Zbl 1364.94179
[46] Zhang, Y.; Qiu, L., From subadditive inequalities of singular values to triangle inequalities of canonical angles, SIAM J. Matrix Anal. Appl., 31, 4, 1606-1620, (2010) · Zbl 1206.15018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.