×

Perturbation analysis of low-rank matrix stable recovery. (English) Zbl 1471.15012

Summary: In this paper, we bring forward a completely perturbed nuclear norm minimization method to tackle a formulation of completely perturbed low-rank matrices recovery. In view of the matrix version of the restricted isometry property (RIP) and the Frobenius-robust rank null space property (FRNSP), this paper extends the investigation to a completely perturbed model taking into consideration not only noise but also perturbation, derives sufficient conditions guaranteeing that low-rank matrices can be robustly and stably reconstructed under the completely perturbed scenario, as well as finally presents an upper bound estimation of recovery error. The upper bound estimation can be described by two terms, one concerning the total noise, and another regarding the best \(r\)-approximation error. Specially, we not only improve the condition corresponding with RIP, but also ameliorate the upper bound estimation in case the results reduce to the general case. Furthermore, in the case of \(\mathcal{E}=0\), the obtained conditions are optimal.

MSC:

15A29 Inverse problems in linear algebra
47A55 Perturbation theory of linear operators
60E05 Probability distributions: general theory
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A20 Sampling theory in information and communication theory

Software:

softImpute
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blumensath, T. and Davies, M., Compressed sensing and source separation, in Int. Conf. Independent Component Analysis Signal Separation, Vol. 4666 (Springer Verlag, 2007), pp. 341-348. · Zbl 1173.94353
[2] Cai, T. and Zhang, A., Sharp RIP bound for sparse signal and low-rank matrix recovery, Appl. Comput. Harmon. Anal.35(1) (2013) 74-93. · Zbl 1310.94021
[3] Cai, T. and Zhang, A., Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inform. Theory60(1) (2014) 122-132. · Zbl 1364.94114
[4] Candès, E.et al., Robust principal component analysis?J. ACM58(11) (2011) 1-37. · Zbl 1327.62369
[5] Candès, E. and Plan, Y., Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Trans. Inform. Theory57(4) (2011) 2342-2359. · Zbl 1366.90160
[6] Chang, X.et al., Unified low-rank matrix estimate via penalized matrix least squares approximation, IEEE Trans. Neural Netw. Learn. Syst.30(2) (2019) 474-485.
[7] Chen, W. and Li, Y., Stable recovery of low-rank matrix via nonconvex Schatten \(p\)-minimization, Sci. China Math.58(12) (2015) 2643-2654. · Zbl 1342.90141
[8] Foucart, S. and Rauhut, H., A Mathematical Introduction to Compressive Sensing (Springer Science+Business Media, 2013). · Zbl 1315.94002
[9] Gao, Y., Han, X. and Ma, M., Recovery of low-rank matrices based on the rank null space properties, Int. J. Wavelets, Multiresolut. Inf. Process.15(4) (2017) 1-19. · Zbl 1408.15018
[10] Gao, Y., Yue, S. and Huang, Y., Stability of \(l_q\)-analysis based dual frame with Weibull matrices for \(0<q\leq1\), Int. J. Wavelets, Multiresolut. Inf. Process.15(1) (2017) 1-15. · Zbl 1371.15037
[11] Gilbert, A. C.et al., One sketch for all: fast algorithms for compressed sensing, in Proc. 39th Annual ACM Symp. on Theory of Computing (San Diego, California, USA, 2007), pp. 237-246. · Zbl 1232.94008
[12] Herman, M. A. and Strohmer, T., High-resolution radar via compressed sensing, IEEE Trans Signal Process.57(6) (2009) 2275-2284. · Zbl 1391.94236
[13] Herman, M. A. and Strohmer, T., General deviants: An analysis of perturbations in compressed sensing, IEEE J. Sel. Top. Signal Process.4(2) (2010) 342-349.
[14] Horn, R. and Johnson, C., Topics in Matrix Analysis (Cambridge University Press, 1991). · Zbl 0729.15001
[15] Kabanava, M.et al., Stable low-rank matrix recovery via null space properties, Inf. Infer.5(4) (2016) 405-441. · Zbl 1388.94018
[16] Kong, L. and Xiu, N., Exact low-rank matrix recovery via nonconvex Schatten \(p\)-minimization, Asia-Pac. J. Oper. Res.30(3) (2013) 1-13. · Zbl 1273.90257
[17] Lin, J. and Li, S., Convergence of projected Landweber iteration for matrix rank minimization, Appl. Comput. Harmon. Anal.36(2) (2014) 316-325. · Zbl 1302.65144
[18] Mazumder, R., Hastie, T. and Tibshirani, R., Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res.11 (2010) 2287-2322. · Zbl 1242.68237
[19] Mohan, K. and Fazel, M., New restricted isometry results for noisy low-rank recovery, in IEEE Int. Symp. on Information Theory Proceedings (ISIT) (2010), pp. 1573-1577.
[20] Recht, B., Fazel, M. and Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev.52(3) (2010) 471-501. · Zbl 1198.90321
[21] Wang, H. and Li, S., The bounds of restricted isometry constants for low rank matrices recovery, Sci. China Math.56(6) (2013) 1117-1127. · Zbl 1273.90156
[22] Wang, J.et al., Group sparse recovery in impulsive noise via alternating direction method of multipliers, Appl. Comput. Harmon. Anal.49(3) (2020) 1063-5203.
[23] Wang, J.et al., A nonconvex penalty function with integral convolution approximation for compressed sensing, Signal Process.158 (2019) 116-128.
[24] W. Wang, F, Zhang and J. Wang, Low-rank matrix recovery via regularized nuclear norm minimization, preprint (2019), arXiv:1903.01053. · Zbl 1469.65090
[25] Wang, Y.et al., Compressive sensing of hyperspectral images via joint tensor tucker decomposition and weighted total variation regularization, IEEE Geosci. Remote Sens. Lett.14(12) (2017) 2457-2461.
[26] Zhang, J., Wang, J. and Wang, W., A perturbation analysis of block-sparse compressed sensing via mixed \(\ell_2/ \ell_1\) minimization, Int. J. Wavelets, Multiresolut. Inf. Process.14(4) (2016) 1-11. · Zbl 1366.94135
[27] Zhang, M., Huang, Z. and Zhang, Y., Restricted \(p\)-isometry properties of nonconvex matrix recovery, IEEE Trans. Inform. Theory59(7) (2013) 4316-4323. · Zbl 1364.94179
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.