2013

Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming

Chen, Yuxin, Chi, Yuejie, Goldsmith, Andrea

Understand

Statistical inference and information processing of high-dimensional data often require efficient and accurate estimation of their second-order statistics.

With rapidly changing data, limited processing power and storage at the acquisition devices, it is desirable to extract the covariance structure from a single pass over the data and a small number of stored measurements.
In this paper, we explore a quadratic (or rank-one) measurement model which imposes minimal memory requirements and low computational complexity during the sampling process, and is shown to be optimal in preserving various low-dimensional covariance structures.
Specifically, four popular structural assumptions of covariance matrices, namely low rank, Toeplitz low rank, sparsity, jointly rank-one and sparse structure, are investigated, while recovery is achieved via convex relaxation paradigms for the respective structure.

Built on

U. Grenander and G. Szegő, Toeplitz forms and their applications . Univ of California Press, 1958
1958
Earlier work this paper cites.
R. G. Gallager, “Information theory and reliable communication,” 1968
1968
Earlier work this paper cites.
D. L. Hanson and F. T. Wright, “A bound on tail probabilities for quadratic forms in independent random variables,” The Annals of Mathematical Statistics , vol. 42, no. 3, pp. 1079–1083, 1971
1971
Earlier work this paper cites.
E. Oja, Subspace methods of pattern recognition . Research Studies Press England, 1983, vol. 4
1983
Earlier work this paper cites.
R. Roy and T. Kailath, “ESPRIT-estimation of signal parameters via rotational invariance techniques,” IEEE Transactions on Acoustics, Speech and Signal Processing , vol. 37, no. 7, pp. 984 –995, Jul 1989
1989
Earlier work this paper cites.
G. W. Stewart and J.-g. Sun, “Matrix perturbation theory,” 1990
1990
Earlier work this paper cites.
M. Ledoux and M. Talagrand, Probability in Banach Spaces: isoperimetry and processes . Springer, 1991, vol. 23
1991
Earlier work this paper cites.
L. L. Scharf and B. Friedlander, “Matched subspace detectors,” IEEE Transactions on Signal Processing , vol. 42, no. 8, pp. 2146–2157, 1994
1994
Earlier work this paper cites.
M. Raymer, M. Beck, and D. McAlister, “Complex wave-field reconstruction using phase-space tomography,” Physical review letters , vol. 72, no. 8, p. 1137, 1994
1994
Earlier work this paper cites.
M. Talagrand, “Majorizing measures: the generic chaining,” The Annals of Probability , pp. 1049–1103, 1996
1996
Earlier work this paper cites.
M. Brand, “Incremental singular value decomposition of uncertain data with missing values,” in ECCV 2002 . Springer, 2002, pp. 707–720
2002
Earlier work this paper cites.
S. Muthukrishnan, Data streams: Algorithms and applications . Now Publishers Inc, 2005
2005
Earlier work this paper cites.
I. M. Johnstone, “High dimensional statistical inference and random matrices,” in Proceedings of the International Congress of Mathematicians: Madrid, August 22-30, 2006: invited lectures , 2006, pp. 307–333
2006
Earlier work this paper cites.
D. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory , vol. 52, no. 4, pp. 1289 –1306, April 2006
2006
Earlier work this paper cites.
E. J. Candes and T. Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies?” IEEE Transactions on Information Theory , vol. 52, no. 12, pp. 5406–5425, Dec. 2006
2006
Earlier work this paper cites.
R. C. Daniels and R. W. Heath, “60 GHz wireless communications: emerging requirements and design recommendations,” IEEE Vehicular Technology Magazine , vol. 2, no. 3, pp. 41–50, 2007
2007
Earlier work this paper cites.
N. Karoui, “Operator norm consistent estimation of large-dimensional sparse covariance matrices,” The Annals of Statistics , pp. 2717–2756, 2008
2008
Earlier work this paper cites.
M. Rudelson and R. Vershynin, “On sparse reconstruction from Fourier and Gaussian measurements,” Communications on Pure and Applied Mathematics , vol. 61, no. 8, pp. 1025–1045, 2008
2008
Earlier work this paper cites.
E. J. Candès, “The restricted isometry property and its implications for compressed sensing,” Comptes Rendus Mathematique , vol. 346, no. 9, pp. 589–592, 2008
2008
Earlier work this paper cites.
R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof of the restricted isometry property for random matrices,” Constructive Approximation , vol. 28, no. 3, pp. 253–263, 2008
2008
Earlier work this paper cites.
E. J. Candes and B. Recht, “Exact matrix completion via convex optimization,” Foundations of Computational Mathematics , vol. 9, no. 6, pp. 717–772, April 2009
2009
Earlier work this paper cites.

Similar

S. Jafarpour, W. Xu, B. Hassibi, and R. Calderbank, “Efficient and robust compressed sensing using optimized expander graphs,” IEEE Transactions on Information Theory , vol. 55, no. 9, pp. 4299–4308, 2009
2009
Cited alongside, same era.
J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg, and R. G. Baraniuk, “Beyond nyquist: Efficient sampling of sparse bandlimited signals,” Information Theory, IEEE Transactions on , vol. 56, no. 1, pp. 520–544, 2010
2010
Cited alongside, same era.
L. Balzano, R. Nowak, and B. Recht, “Online identification and tracking of subspaces from highly incomplete information,” Proc. Allerton 2010 , 2010
2010
Cited alongside, same era.
B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM Review , vol. 52, no. 3, pp. 471–501, 2010
2010
Cited alongside, same era.
G. Leus and Z. Tian, “Recovering second-order statistics from compressive measurements,” in Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), , 2011, pp. 337–340
2011
Cited alongside, same era.
Y. Shechtman, Y. C. Eldar, A. Szameit, and M. Segev, “Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing,” Optics express , vol. 19, no. 16, pp. 14 807–14 822, 2011
2011
Cited alongside, same era.
D. Gross, “Recovering low-rank matrices from few coefficients in any basis,” IEEE Transactions on Information Theory , vol. 57, no. 3, pp. 1548–1566, March 2011
2011
Cited alongside, same era.
Y.-K. Liu, “Universal low-rank matrix recovery from pauli measurements,” in Advances in Neural Information Processing Systems , 2011, pp. 1638–1646
2011
Cited alongside, same era.
H. Ohlsson, A. Y. Yang, R. Dong, and S. S. Sastry, “Compressive phase retrieval from squared output measurements via semidefinite programming,” arXiv preprint arXiv:1111.6323 , 2011
Original
2011
Cited alongside, same era.
E. Candes and Y. Plan, “Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements,” IEEE Transactions on Information Theory , vol. 57, no. 4, pp. 2342–2359, 2011
2011
Cited alongside, same era.
E. Candes and Y. Plan, “A probabilistic and RIPless theory of compressed sensing,” IEEE Transactions on Information Theory , vol. 57, no. 11, pp. 7235–7254, 2011
2011
Cited alongside, same era.
D. D. Ariananda and G. Leus, “Compressive wideband power spectrum estimation,” IEEE Transactions on Signal Processing , vol. 60, no. 9, pp. 4775–4789, 2012
2012
Cited alongside, same era.

Then

D. Hsu, S. M. Kakade, and T. Zhang, “A tail inequality for quadratic forms of sub-Gaussian random vectors,” Electronic Communications in Probability , vol. 17, no. 52, 2012
2012
Later among the works it cites.
A. Jung, G. Taubock, and F. Hlawatsch, “Compressive spectral estimation for nonstationary random processes,” IEEE Transactions on Information Theory , vol. 59, no. 5, May 2013
2013
Closest in time.
Y. Shechtman, A. Beck, and Y. C. Eldar, “GESPAR: Efficient phase retrieval of sparse signals,” arXiv preprint arXiv:1301.1018 , 2013
Original
2013
Closest in time.
P. Netrapalli, P. Jain, and S. Sanghavi, “Phase retrieval using alternating minimization,” Advances in Neural Information Processing Systems (NIPS) , 2013
2013
Closest in time.
E. J. Candes and X. Li, “Solving quadratic equations via PhaseLift when there are about as many equations as unknowns,” Foundations of Computational Mathematics , 2013
2013
Closest in time.
X. Li and V. Voroninski, “Sparse signal recovery from quadratic measurements via convex programming,” SIAM Journal on Mathematical Analysis , 2013
2013
Closest in time.
D. Romero and G. Leus, “Wideband spectrum sensing from compressed measurements using spectral prior information,” Signal Processing, IEEE Transactions on , vol. 61, no. 24, pp. 6232–6246, 2013
2013
Closest in time.
G. Dasarathy, P. Shah, B. N. Bhaskar, and R. Nowak, “Sketching sparse matrices,” arXiv preprint arXiv:1303.6544 , 2013
Original
2013
Closest in time.
A. Beck and Y. C. Eldar, “Sparsity constrained nonlinear optimization: Optimality conditions and algorithms,” to appear in SIAM Optimization , 2013
2013
Closest in time.
I. Mitliagkas, C. Caramanis, and P. Jain, “Memory limited, streaming PCA,” Advances in Neural Information Processing Systems (NIPS) , 2013
2013
Closest in time.
Y. Chi, Y. Eldar, and R. Calderbank, “PETRELS: Parallel subspace estimation and tracking by recursive least squares from partial observations,” Signal Processing, IEEE Transactions on , vol. 61, no. 23, pp. 5947–5959, 2013
2013
Closest in time.
M. Rudelson and R. Vershynin, “Hanson-Wright inequality and sub-Gaussian concentration,” arXiv preprint arXiv:1306.2872 , June 2013
Original
2013
Closest in time.
Y. Chen, Y. Chi, and A. Goldsmith, “Estimation of simultaneously structured covariance matrices from quadratic measurements,” in International Conference on Acoustics, Speech, and Signal Processing (ICASSP) , Florence, Italy, May 2014, pp. 7669 – 7673
2014
Closest in time.
Y. Chen, X. Yi, and C. Caramanis, “A convex formulation for mixed regression with two components: Minimax optimal rates,” in The Conference on Learning Theory (COLT) , 2014
2014
Closest in time.
Y. Chen and Y. Chi, “Robust spectral compressed sensing via structured matrix completion,” IEEE Trans. on Information Theory , vol. 60, no. 10, pp. 6576 – 6601, October 2014
2014
Closest in time.
T. T. Cai and A. Zhang, “Rop: Matrix recovery via rank-one projections,” arXiv preprint arXiv:1310.5791 , 2014
Original
2014
Closest in time.
E. Candes, X. Li, and M. Soltanolkotabi, “Phase retrieval via Wirtinger flow: Theory and algorithms,” IEEE Transactions on Information Theory , vol. 61, no. 4, pp. 1985–2007, April 2015
2015
Closest in time.
P. Schniter and S. Rangan, “Compressive phase retrieval via generalized approximate message passing,” Signal Processing, IEEE Transactions on , vol. 63, no. 4, pp. 1043–1055, Feb 2015
2015
Closest in time.
G. Aubrun, “On almost randomizing channels with a short Kraus decomposition,” Communications in Mathematical Physics , vol. 288, no. 3, pp. 1103–1116, 2009
Original
2015
Closest in time.
——, “Robust and universal covariance estimation from quadratic measurements via convex programming,” in International Symposium on Information Theory (ISIT) , Honolulu, HI, June 2014, pp. 2017 – 2021
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…