×

Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements. (English) Zbl 1386.94020

Summary: In this paper, we consider the problem of estimating simultaneously low-rank and row-wise sparse matrices from nested linear measurements, where the linear operator consists of the product of a linear operator \(\mathcal W\) and a matrix \(\boldsymbol{\Psi}\). Leveraging the nested structure of the measurement operator, we propose a computationally efficient two-stage algorithm for estimating the simultaneously structured target matrix. Assuming that \(\mathcal{W}\) is a restricted isometry for low-rank matrices and \(\boldsymbol{\Psi}\) is a restricted isometry for row-wise sparse matrices, we establish an accuracy guarantee that holds uniformly for all sufficiently low-rank and row-wise sparse matrices with high probability. Furthermore, using standard tools from information theory, we establish a minimax lower bound for estimation of simultaneously low-rank and row-wise sparse matrices from linear measurements that need not be nested. The accuracy bounds established for the algorithm, that also serve as a minimax upper bound, differ from the derived minimax lower bound merely by a polylogarithmic factor of the dimensions. Therefore, the proposed algorithm is nearly minimax optimal. We also discuss some applications of the proposed observation model and evaluate our algorithm through numerical simulation.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65F50 Computational methods for sparse matrices

References:

[1] Amini, A. A.; Wainwright, M. J., High-dimensional analysis of semidefinite relaxations for sparse principal components, Ann. Statist., 37, 2921, (2009) · Zbl 1173.62049 · doi:10.1214/08-AOS664
[2] Bahmani, S.; Romberg, J., Efficient compressive phase retrieval with constrained sensing vectors, 531, (2015)
[3] Bahmani, S.; Romberg, J., Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation, SIAM J. Imaging Sci., 8, 2238, (2015) · Zbl 1330.94006 · doi:10.1137/141002165
[4] Bahmani, S.; Romberg, J., Sketching for simultaneously sparse and low-rank covariance matrices, 360, (2015)
[5] Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 263, (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x
[6] Becker, S. R.; Candès, E. J.; Grant, M. C., Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3, 218, (2011) · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5
[7] Berthet, Q.; Rigollet, P., Complexity theoretic lower bounds for sparse principal component detection, 1066, (2013)
[8] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 274, (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002
[9] Buja, A.; Ma, Z.; Yang, D., Optimal denoising of simultaneously sparse and low-rank matrices in high dimensions, 447, (2013)
[10] Cai, T.; Ma, Z.; Wu, Y., Optimal estimation and rank detection for sparse spiked covariance matrices, Probab. Theory Related Fields, 161, 815, (2015) · Zbl 1314.62130 · doi:10.1007/s00440-014-0562-z
[11] Cai, T. T.; Ma, Z.; Wu, Y., Sparse PCA: optimal rates and adaptive estimation, Ann. Statist., 41, 3110, (2013) · Zbl 1288.62099 · doi:10.1214/13-AOS1178
[12] Candès, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval via Wirtinger flow: theory and algorithms, IEEE Trans. Inform. Theory, 61, 2007, (2015) · Zbl 1359.94069 · doi:10.1109/TIT.2015.2399924
[13] 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, 2359, (2011) · Zbl 1366.90160 · doi:10.1109/TIT.2011.2111771
[14] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 772, (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[15] Candès, E. J.; Strohmer, T.; Voroninski, V., PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 66, 1274, (2013) · Zbl 1335.94013 · doi:10.1002/cpa.v66.8
[16] Chen, Y.; Chi, Y.; Goldsmith, A., Exact and stable covariance estimation from quadratic sampling via convex programming, IEEE Trans. Inform. Theory, 61, 4059, (2015) · Zbl 1359.62181 · doi:10.1109/TIT.2015.2429594
[17] d’Aspremont, A.; ElGhaoui, L.; Jordan, M. I.; Lanckriet, G. R. G., A direct formulation for sparse PCA using semidefinite programming, SIAM Rev., 49, 448, (2007) · Zbl 1128.90050 · doi:10.1137/050645506
[18] Daubechies, I., Symmetry for compactly supported wavelet bases, Ten Lectures on Wavelets, (1992)
[19] Eldar, Y. C.; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 5316, (2009) · Zbl 1367.94087 · doi:10.1109/TIT.2009.2030471
[20] Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 1566, (2011) · Zbl 1366.94103 · doi:10.1109/TIT.2011.2104999
[21] Iwen, M.; Viswanathan, A.; Wang, Y., Robust sparse phase retrieval made easy, Appl. Comput. Harmon. Anal., (2015)
[22] Johnstone, I. M.; Lu, A. Y., On consistency and sparsity for principal components analysis in high dimensions, J. Amer. Statist. Assoc., 104, 693, (2009) · Zbl 1388.62174 · doi:10.1198/jasa.2009.0121
[23] Koltchinskii, V.; Lounici, K.; Tsybakov, A. B., Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Ann. Statist., 39, 2329, (2011) · Zbl 1231.62097 · doi:10.1214/11-AOS894
[24] Kueng, R.; Rauhut, H.; Terstiege, U., Low-rank matrix recovery from rank one measurements, Appl. Comput. Harmon. Anal., (2015)
[25] Laurent, B.; Massart, P., Adaptive estimation of a quadratic functional by model selection, Ann. Statist., 28, 1338, (2000) · Zbl 1105.62328 · doi:10.1214/aos/1015957395
[26] Lee, K.; Wu, Y.; Bresler, Y., (2013)
[27] Li, X.; Voroninski, V., Sparse signal recovery from quadratic measurements via convex programming, SIAM J. Math. Anal., 45, 3033, (2013) · Zbl 1320.94023 · doi:10.1137/120893707
[28] Ma, Z.; Sun, T., (2014)
[29] Massart, P., (2007)
[30] Mendelson, S., Learning without concentration, 39, (2014)
[31] Moravec, M. L.; Romberg, J. K.; Baraniuk, R. G., Compressive phase retrieval, 6701, 11, (2007)
[32] Netrapalli, P.; Jain, P.; Sanghavi, S., (2013)
[33] Ohlsson, H.; Yang, A.; Dong, R.; Sastry, S., CPRL—an extension of compressive sensing to the phase retrieval problem, 1375, (2012)
[34] Oymak, S.; Jalali, A.; Fazel, M.; Eldar, Y.; Hassibi, B., Simultaneously structured models with application to sparse and low-rank matrices, IEEE Trans. Inform. Theory, 61, 2908, (2015) · Zbl 1359.94150 · doi:10.1109/TIT.2015.2401574
[35] Raskutti, G.; Wainwright, M.; Yu, B., Minimax rates of estimation for high-dimensional linear regression over \[ℓ_q\]-balls, IEEE Trans. Inform. Theory, 57, 6994, (2011) · Zbl 1365.62276 · doi:10.1109/TIT.2011.2165799
[36] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 501, (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[37] Rohde, A.; Tsybakov, A. B., Estimation of high-dimensional low-rank matrices, Ann. Statist., 39, 930, (2011) · Zbl 1215.62056 · doi:10.1214/10-AOS860
[38] Shechtman, Y.; Beck, A.; Eldar, Y. C., GESPAR: efficient phase retrieval of sparse signals, IEEE Trans. Signal Process., 62, 938, (2014) · Zbl 1394.94522 · doi:10.1109/TSP.2013.2297687
[39] Shechtman, Y.; Eldar, Y. C.; Szameit, A.; Segev, M., Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing, Opt. Express, 19, 14822, (2011) · doi:10.1364/OE.19.014807
[40] Tang, G.; Recht, B., Convex blind deconvolution with random masks, (2014)
[41] Tropp, J. A., Convex recovery of a structured signal from independent random linear measurements, Sampling Theory, a Renaissance: Compressive Sensing and Other Developments, 101, (2015) · Zbl 1358.94034
[42] Tsybakov, A. B., Introduction to Nonparametric Estimation, (2008)
[43] Vu, V. Q.; Cho, J.; Lei, J.; Rohe, K., Fantope projection and selection: a near-optimal convex relaxation of sparse PCA, 2678, (2013)
[44] Wang, Z.; Lu, H.; Liu, H., Tighten after relax: minimax-optimal sparse PCA in polynomial time, 3391, (2014)
[45] Yang, J.; Zhang, Y., Alternating direction algorithms for \[ℓ_1\]-problems in compressive sensing, SIAM J. Sci. Comput., 33, 278, (2011) · Zbl 1256.65060 · doi:10.1137/090777761
[46] Yapar, Ç.; Pohl, V.; Boche, H., Fast compressive phase retrieval from Fourier measurements, 3271, (2015)
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.