Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming

DOI10.1109/TIT.2015.2429594MaRDI QIDQ2977389zbMATH OpenOpenAlexFDO

Authors Yuxin Chen, Yuejie Chi, Andrea J. Goldsmith

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0807

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Estimation in multivariate analysis (62H12) Convex programming (90C25)

Abstract: 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. The proposed quadratic sampling framework has a variety of potential applications including streaming data processing, high-frequency wireless communication, phase space tomography and phase retrieval in optics, and non-coherent subspace detection. Our method admits universally accurate covariance estimation in the absence of noise, as soon as the number of measurements exceeds the information theoretic limits. We also demonstrate the robustness of this approach against noise and imperfect structural assumptions. Our analysis is established upon a novel notion called the mixed-norm restricted isometry property (RIP-$el{l}_2/el{l}_1$), as well as the conventional RIP-$el{l}_2/el{l}_2$ for near-isotropic and bounded measurements. In addition, our results improve upon the best-known phase retrieval (including both dense and sparse signals) guarantees using PhaseLift with a significantly simpler approach.

Cited in

(39)

• Subgradient methods for sharp weakly convex functions
• Learning general sparse additive models from point queries in high dimensions
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Compressive total variation for image reconstruction and restoration
• Complex phase retrieval from subgaussian measurements
• Compressed covariance estimation with automated dimension learning
• ROP: matrix recovery via rank-one projections
• The local convexity of solving systems of quadratic equations
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• Low rank matrix recovery from rank one measurements
• Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements
• Stable low-rank matrix recovery via null space properties
• Stochastic model-based minimization of weakly convex functions
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Low rank matrix recovery with adversarial sparse noise
• Sample Efficient Toeplitz Covariance Estimation
• Norm and trace estimation with random rank-one vectors
• Communication-Efficient Distributed Eigenspace Estimation
• An optimal-storage approach to semidefinite programming using approximate complementarity
• Nonconvex Robust Low-Rank Matrix Recovery
• Covariate Information Number for Feature Screening in Ultrahigh-Dimensional Supervised Problems
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Matrix recovery from nonconvex regularized least absolute deviations
• Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
• Optimal sparse phase retrieval via a quasi-Bayesian approach
• Robust outlier bound condition to phase retrieval with adversarial sparse outliers
• Approximating positive homogeneous functions with scale invariant neural networks
• First-order methods for nonsmooth nonconvex functional constrained optimization with or without Slater points
• A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth
• Efficient projection-free online convex optimization using stochastic gradients
• The condition number in phase retrieval from intensity measurements
• Sparse signal recovery from phaseless measurements via _1² - _2² minimization

This page was built for publication: Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977389)