Compressed sensing of low-rank plus sparse matrices. (English) Zbl 1508.65043
Summary: Expressing a matrix as the sum of a low-rank matrix plus a sparse matrix is a flexible model capturing global and local features in data. This model is the foundation of robust principle component analysis [E. J. Candès et al., J. ACM 58, No. 3, Article No. 11, 37 p. (2011; Zbl 1327.62369); V. Chandrasekaran et al., SIAM J. Optim. 21, No. 2, 572–596 (2011; Zbl 1226.90067)], and popularized by dynamic-foreground/static-background separation [T. Bouwmans et al., Comput. Sci. Rev. 23, 1–71 (2017; Zbl 1398.68572)]. Compressed sensing, matrix completion, and their variants [Y. C. Eldar and G. Kutyniok, Compressed sensing: theory and applications. Cambridge: Cambridge University Press (2012); S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing. New York, NY: Birkhäuser/Springer (2013; Zbl 1315.94002)] have established that data satisfying low complexity models can be efficiently measured and recovered from a number of measurements proportional to the model complexity rather than the ambient dimension. This manuscript develops similar guarantees showing that \(m \times n\) matrices that can be expressed as the sum of a rank-\(r\) matrix and a \(s\)-sparse matrix can be recovered by computationally tractable methods from \(\mathcal{O}(r(m + n - r) + s) \log (m n / s)\) linear measurements. More specifically, we establish that the low-rank plus sparse matrix set is closed provided the incoherence of the low-rank component is upper bounded as \(\mu < \sqrt{mn} /(r \sqrt{s})\), and subsequently, the restricted isometry constants for the aforementioned matrices remain bounded independent of problem size provided \(p/mn, s/p\), and \(r(m + n-r) / p\) remain fixed. Additionally, we show that semidefinite programming and two non-convex hard threshold gradient descent algorithms, NIHT and NAHT, converge to the measured matrix provided the measurement operator’s RICs are sufficiently small. These results also provably solve the convex formulation of Robust PCA with the asymptotically optimal fraction of corruptions \(\alpha = \mathcal{O} (1/(\mu r))\), where \(s = \alpha^2 mn\), and improve the previously known guarantees by not requiring that the fraction of corruptions is spread in every column and row by being upper bounded with \(\alpha\). Numerical experiments illustrating these results are shown for synthetic problems, dynamic-foreground/static-background separation, and multispectral imaging.
MSC:
| 65F55 | Numerical methods for low-rank matrix approximation; matrix compression |
| 41A29 | Approximation with constraints |
| 62H25 | Factor analysis and principal components; correspondence analysis |
| 65F10 | Iterative numerical methods for linear systems |
| 65J20 | Numerical solutions of ill-posed problems in abstract spaces; regularization |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C22 | Semidefinite programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
matrix sensing; low-rank plus sparse matrix; robust PCA; restricted isometry property; non-convex methodsReferences:
| [1] | Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58, 3, 1-37 (2011) · Zbl 1327.62369 |
| [2] | Chandrasekaran, V.; Sanghavi, S.; Parrilo, P. A.; Willsky, A. S., Rank-sparsity incoherence for matrix decomposition, SIAM J. Optim., 21, 2, 572-596 (2011) · Zbl 1226.90067 |
| [3] | Bouwmans, T.; Sobral, A.; Javed, S.; Jung, S. K.; Zahzah, E.-H., Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset, Comput. Sci. Rev., 23, 1-71 (2017) · Zbl 1398.68572 |
| [4] | Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge University Press |
| [5] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis (2013), Springer New York: Springer New York New York, NY · Zbl 1315.94002 |
| [6] | Donoho, D., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 |
| [7] | Candes, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 |
| [8] | Candes, E.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121 |
| [9] | Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124 |
| [10] | Candes, E. J.; Tao, T., The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inf. Theory, 56, 5, 2053-2080 (2010) · Zbl 1366.15021 |
| [11] | 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 |
| [12] | Candès, E. J.; Fernandez-Granda, C., Towards a mathematical theory of super-resolution, Commun. Pure Appl. Math., 67, 6, 906-956 (2014) · Zbl 1350.94011 |
| [13] | Duval, V.; Peyré, G., Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., 15, 5, 1315-1355 (2015) · Zbl 1327.65104 |
| [14] | Eftekhari, A.; Tanner, J.; Thompson, A.; Toader, B.; Tyagi, H., Sparse non-negative super-resolution — simplified and stabilised, Appl. Comput. Harmon. Anal., 1, 1-65 (2019) |
| [15] | Chi, Y.; Ferreira Da Costa, M., Harnessing sparsity over the continuum: atomic norm minimization for superresolution, IEEE Signal Process. Mag., 37, 2, 39-57 (2020) |
| [16] | Gu, S.; Zhang, L.; Zuo, W.; Feng, X., Weighted nuclear norm minimization with application to image denoising, (2014 IEEE Conference on Computer Vision and Pattern Recognition (2014), IEEE), 2862-2869 |
| [17] | Gogna, A.; Shukla, A.; Agarwal, H. K.; Majumdar, A., Split Bregman algorithms for sparse / joint-sparse and low-rank signal recovery: application in compressive hyperspectral imaging, (2014 IEEE International Conference on Image Processing (ICIP) (2014), IEEE), 1302-1306 |
| [18] | Chen, Y.; Guo, Y.; Wang, Y.; Wang, D.; Peng, C.; He, G., Denoising of hyperspectral images using nonconvex low rank matrix approximation, IEEE Trans. Geosci. Remote Sens., 55, 9, 5366-5380 (2017) |
| [19] | Wei, W.; Zhang, L.; Zhang, Y.; Wang, C.; Tian, C., Hyperspectral image denoising from an incomplete observation, (2015 International Conference on Orange Technologies (ICOT) (2015), IEEE), 177-180 |
| [20] | Luan, X.; Fang, B.; Liu, L.; Yang, W.; Qian, J., Extracting sparse error of robust PCA for face recognition in the presence of varying illumination and occlusion, Pattern Recognit., 47, 2, 495-508 (2014) |
| [21] | Wright, J.; Yang, A.; Ganesh, A.; Sastry, S.; Ma, Yi, Robust face recognition via sparse representation, IEEE Trans. Pattern Anal. Mach. Intell., 31, 2, 210-227 (2009) |
| [22] | Xu, F.; Han, J.; Wang, Y.; Chen, M.; Chen, Y.; He, G.; Hu, Y., Dynamic magnetic resonance imaging via nonconvex low-rank matrix approximation, IEEE Access, 5, 1958-1966 (2017) |
| [23] | Gao, H.; Cai, J.-F.; Shen, Z.; Zhao, H., Robust principal component analysis-based four-dimensional computed tomography, Phys. Med. Biol., 56, 11, 3181-3198 (2011) |
| [24] | Vary, S.; Daglayan, H.; Jacques, L.; Absil, P.-A., Low-rank plus sparse trajectory decomposition for direct exoplanet imaging (Jan. 2023) |
| [25] | Oreifej, O.; Li, X.; Shah, M., Simultaneous video stabilization and moving object detection in turbulence, IEEE Trans. Pattern Anal. Mach. Intell., 35, 2, 450-462 (2013) |
| [26] | Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 3, 253-263 (2008) · Zbl 1177.15015 |
| [27] | Tanner, J.; Thompson, A.; Vary, S., Matrix rigidity and the ill-posedness of robust PCA and matrix completion, SIAM J. Math. Data Sci., 1, 3, 537-554 (2019) · Zbl 1502.62074 |
| [28] | Hsu, D.; Kakade, S. M.; Zhang, T., Sparse corruptions, IEEE Trans. Inf. Theory, 57, 11, 7221-7234 (2011) · Zbl 1365.15018 |
| [29] | Netrapalli, P.; Niranjan, U. N.; Sanghavi, S.; Anandkumar, A.; Jain, P., Non-convex robust PCA, (Advances in Neural Information Processing Systems 27 (NIPS 2014) (2014)) |
| [30] | Blumensath, T.; Davies, M., Normalized iterative hard thresholding: guaranteed stability and performance, IEEE J. Sel. Top. Signal Process., 4, 2, 298-309 (2010) |
| [31] | Tanner, J.; Wei, K., Normalized iterative hard thresholding for matrix completion, SIAM J. Sci. Comput., 35, 5, S104-S125 (2013) · Zbl 1282.65043 |
| [32] | Hsu, D.; Kakade, S. M.; Zhang, T., Robust matrix decomposition with sparse corruptions, IEEE Trans. Inf. Theory, 57, 11, 7221-7234 (2011) · Zbl 1365.15018 |
| [33] | Chen, Y.; Jalali, A.; Sanghavi, S.; Caramanis, C., Low-rank matrix recovery from errors and erasures, IEEE Trans. Inf. Theory, 59, 7, 4324-4337 (2013) |
| [34] | Ailon, N.; Chazelle, B., The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39, 1, 302-322 (2009) · Zbl 1185.68327 |
| [35] | Krahmer, F.; Ward, R., New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 3, 1269-1281 (2011) · Zbl 1247.15019 |
| [36] | Cai, H.; Cai, J.-F.; Wei, K., Accelerated alternating projections for robust principal component analysis, J. Mach. Learn. Res., 20, 1, 685-717 (2019) · Zbl 1483.62098 |
| [37] | Waters, A. E.; Sankaranarayanan, A. C.; Baraniuk, R. G., SpaRCS: recovering low-rank and sparse matrices from compressive measurements, (Neural Information Processing Systems 24 (NIPS 2011), vol. 2 (2011)), 1089-1097 |
| [38] | Baraniuk, R. G.; Cevher, V.; Duarte, M. F.; Hegde, C., Model-based compressive sensing, IEEE Trans. Inf. Theory, 56, 4, 1982-2001 (2010) · Zbl 1366.94215 |
| [39] | Szarek, S., Metric entropy of homogeneous spaces, Banach Cent. Publ., 43, 1, 395-410 (1998) · Zbl 0927.46047 |
| [40] | Candès, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009 |
| [41] | Yi, X.; Park, D.; Chen, Y.; Caramanis, C., Fast algorithms for robust PCA via gradient descent, (Advances in Neural Information Processing Systems 29 (NIPS 2016) (2016)) |
| [42] | Toh, K. C.; Todd, M. J.; Tütüncü, R. H., SDPT3 — a Matlab software package for semidefinite programming, version 1.3, Optim. Methods Softw., 11, 1-4, 545-581 (1999) · Zbl 0997.90060 |
| [43] | Blanchard, J.; Tanner, J., Performance comparisons of greedy algorithms in compressed sensing, Numer. Linear Algebra Appl., 22, 2, 254-282 (2015) · Zbl 1363.94017 |
| [44] | Blanchard, J. D.; Tanner, J.; Wei, K., CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Inf. Inference (2015) · Zbl 1380.94045 |
| [45] | Stephen, G.; Boyd, M., CVX: Matlab Software for Disciplined Convex Programming (2014), version 2.1 |
| [46] | Zhou, T.; Tao GoDec, D., Randomized low-rank & sparse matrix decomposition in noisy case, (Proceedings of the 28th International Conference on Machine Learning, vol. 35 (2011)), 33-40 |
| [47] | Li, L.; Huang, W.; Gu, I.-H.; Tian, Q., Statistical modeling of complex backgrounds for foreground object detection, IEEE Trans. Image Process., 13, 11, 1459-1472 (2004) |
| [48] | Dimitris, M.; Marden, D.; Shaw, G. A., Hyperspectral image processing for automatic target detection applications, Linc. Lab. J., 14, 1, 79-116 (2003) |
| [49] | Cao, X.; Yue, T.; Lin, X.; Lin, S.; Yuan, X.; Dai, Q.; Carin, L.; Brady, D. J., Computational snapshot multispectral cameras: toward dynamic capture of the spectral world, IEEE Signal Process. Mag., 33, 5, 95-108 (2016) |
| [50] | Degraux, K.; Cambareri, V.; Jacques, L.; Geelen, B.; Blanch, C.; Lafruit, G., Generalized inpainting method for hyperspectral image acquisition, (2015 IEEE International Conference on Image Processing (ICIP) (2015), IEEE), 315-319, Vol. 2015-Decem |
| [51] | Antonucci, G. A.; Vary, S.; Humphreys, D.; Lamb, R. A.; Piper, J.; Tanner, J., Multispectral snapshot demosaicing via non-convex matrix completion, (2019 IEEE Data Science Workshop (DSW) (2019), IEEE), 227-231 |
| [52] | Stein, D.; Beaven, S.; Hoff, L.; Winter, E.; Schaum, A.; Stocker, A., Anomaly detection from hyperspectral imagery, IEEE Signal Process. Mag., 19, 1, 58-69 (2002) |
| [53] | Xu, Y.; Du, B.; Zhang, L.; Cerra, D.; Pato, M.; Carmona, E.; Prasad, S.; Yokoya, N.; Hansch, R.; Le Saux, B., Advanced multi-sensor optical remote sensing for urban land use and land cover classification: outcome of the 2018 IEEE GRSS data fusion contest, IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens., 12, 6, 1709-1724 (2019) |
| [54] | Kemker, R.; Salvaggio, C.; Kanan, C., Algorithms for semantic segmentation of multispectral remote sensing imagery using deep learning, ISPRS J. Photogramm. Remote Sens., 145, 60-77 (2018), June 2017 |
| [55] | Kyrillidis, A.; Cevher, V., Matrix recipes for hard thresholding methods, J. Math. Imaging Vis., 48, 2, 235-265 (2014) · Zbl 1311.90141 |
| [56] | Wei, K., Fast iterative hard thresholding for compressed sensing, IEEE Signal Process. Lett., 22, 5, 593-597 (2015) |
| [57] | Lorentz, G. G.; Golitschek, M. V.; Makovoz, Y., Constructive Approximation: Advanced Problems (1996), Springer-Verlag: Springer-Verlag Berlin Heidelberg · Zbl 0910.41001 |
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.
