Recovering low-rank matrices from few coefficients in any basis

Abstract

We present novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler and more general than previous approaches. It is shown that an unknown (n x n) matrix of rank r can be efficiently reconstructed from only O(n r nu log^2 n) randomly sampled expansion coefficients with respect to any given matrix basis. The number nu quantifies the "degree of incoherence" between the unknown matrix and the basis. Existing work concentrated mostly on the problem of "matrix completion" where one aims to recover a low-rank matrix from randomly selected matrix elements. Our result covers this situation as a special case. The proof consists of a series of relatively elementary steps, which stands in contrast to the highly involved methods previously employed to obtain comparable results. In cases where bounds had been known before, our estimates are slightly tighter. We discuss operator bases which are incoherent to all low-rank matrices simultaneously. For these bases, we show that O(n r nu log n) randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The latter bound is tight up to multiplicative constants.

See also arxiv:0909.3304. v1=v2. v3: Some bounds substantially improved. v4, v5: presentation improved. To appear in IEEE Transactions on Information Theory

References in corpus (1)

• Quantum state tomography via compressed sensing

Cited by in corpus (122)

• Operational Resource Theory of Coherence
• Multidimensional quantum entanglement with large-scale integrated optics
• User-friendly tail bounds for sums of random matrices
• Matrix Completion Methods for Causal Panel Data Models
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Estimation of high-dimensional low-rank matrices
• Guaranteed Matrix Completion via Non-convex Factorization
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Self-Calibration and Biconvex Compressive Sensing
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Incoherence-Optimal Matrix Completion
• Sparse Signal Processing Concepts for Efficient 5G System Design
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Noisy low-rank matrix completion with general sampling distribution
• Permutationally invariant state reconstruction
• Scalable reconstruction of density matrices
• Multipartite entanglement detection from correlation tensors
• Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
• A Partial Derandomization of PhaseLift using Spherical Designs
• The Numerics of Phase Retrieval
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
• Compressed Sensing and Parallel Acquisition
• Blind Identification of Graph Filters
• Efficient and feasible state tomography of quantum many-body systems
• Matrix Completion via Max-Norm Constrained Optimization
• RIPless compressed sensing from anisotropic measurements
• Matrix concentration inequalities via the method of exchangeable pairs
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Concentration for random product formulas
• Quantum state tomography by continuous measurement and compressed sensing
• Guaranteed clustering and biclustering via semidefinite programming
• Multi-Carrier Agile Phased Array Radar
• Recovering quantum gates from few average gate fidelities
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• A Scalable Maximum Likelihood Method for Quantum State Tomography
• Noncommutative Bennett and Rosenthal inequalities
• Experimentally exploring compressed sensing quantum tomography
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
• Experimental compressive phase space tomography
• Scattered Light Imaging: Resolving the substructure of nerve fiber crossings in whole brain sections with micrometer resolution
• Convex recovery of continuous domain piecewise constant images from non-uniform Fourier samples
• Theoretical Analysis for Extended Target Recovery in Randomized Stepped Frequency Radars
• Resolving single molecule structures with nitrogen-vacancy centers in diamond
• Robust PCA with Partial Subspace Knowledge
• Recovery of Future Data via Convolution Nuclear Norm Minimization
• Efficient Pure State Quantum Tomography from Five Orthonormal Bases
• Bootstrapping quantum process tomography via a perturbative ansatz
• Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation
• Guaranteed recovery of quantum processes from few measurements
• Bayesian methods for low-rank matrix estimation: short survey and theoretical study
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Optimal large-scale quantum state tomography with Pauli measurements
• On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
• Matrix completion with deterministic pattern - a geometric perspective
• Compressive gate set tomography
• Rank penalized estimation of a quantum system
• Spectrally Sparse Signal Recovery via Hankel Matrix Completion with Prior Information
• Pseudo-Bayesian Quantum Tomography with Rank-adaptation
• Signal reconstruction from the magnitude of subspace components
• Asymptotic equivalence of quantum state tomography and noisy matrix completion
• Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Simultaneous Sparse Recovery and Blind Demodulation
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• Sparse Blind Deconvolution and Demixing Through ${\ell }_{1,2}$-Minimization
• Error regions in quantum state tomography: computational complexity caused by geometry of quantum states
• Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping
• Improving compressed sensing with the diamond norm
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Enhancing quantum state tomography via resource-efficient attention-based neural networks
• The Role of Topology in Quantum Tomography
• Phase Retrieval Using Unitary 2-Designs
• Quantum system characterization with limited resources
• Spectral thresholding quantum tomography for low rank states
• Semi-device-dependent blind quantum tomography
• Near-optimal matrix recovery from random linear measurements
• Generation of scalable many-body Bell correlations in spin chains with short-range two-body interactions
• A set of $4d-3$ observables to determine any pure qudit state
• Completing Low-Rank Matrices with Corrupted Samples from Few Coefficients in General Basis
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Through the Haze: a Non-Convex Approach to Blind Gain Calibration for Linear Random Sensing Models
• Accelerated 2D magnetic resonance spectroscopy of single spins using matrix completion
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Matrix factorization for multivariate time series analysis
• User-friendly confidence regions for quantum state tomography
• Unrolling SVT to obtain computationally efficient SVT for n-qubit quantum state tomography
• Dynamical Quantum Tomography
• Local asymptotic equivalence of pure quantum states ensembles and quantum Gaussian white noise
• Fundamental Limits of Blind Deconvolution Part II: Sparsity-Ambiguity Trade-offs
• Fundamental Limits of Blind Deconvolution Part I: Ambiguity Kernel
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Concentration properties of fractional posterior in 1-bit matrix completion
• Decomposable Norm Minimization with Proximal-Gradient Homotopy Algorithm
• Optimal tuning-free convex relaxation for noisy matrix completion
• Deep Unfolding of Iteratively Reweighted ADMM for Wireless RF Sensing
• Constrained Quantum Tomography of Semi-Algebraic Sets with Applications to Low-Rank Matrix Recovery
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• A random algorithm for low-rank decomposition of large-scale matrices with missing entries
• Concentration Inequalities for Sums of Markov Dependent Random Matrices
• An efficient adaptive MCMC algorithm for Pseudo-Bayesian quantum tomography
• Estimation of low rank density matrices by Pauli measurements
• Separable Joint Blind Deconvolution and Demixing
• Compressed Sensing Tomography for qudits in Hilbert spaces of non-power-of-two dimensions
• Digital Quantum Simulation of Scalar Yukawa Coupling
• Phase retrieval using random cubatures and fusion frames of positive semidefinite matrices
• AutoGFI: Streamlined Generalized Fiducial Inference for Modern Inference Problems in Models with Additive Errors
• Optimal observables to determine entanglement of a two qubit state
• Low rank estimation of smooth kernels on graphs
• Tight Risk Bound for High Dimensional Time Series Completion
• Corrupted sensing quantum state tomography
• A direct proof of a unified law of robustness for Bregman divergence losses
• Enhanced Compressive Threshold Quantum State Tomography for Qudit Systems
• Measuring entanglement without local addressing in quantum many-body simulators via spiral quantum state tomography
• Information-theoretic Bounds on Matrix Completion under Union of Subspaces Model
• Misclassification excess risk bounds for 1-bit matrix completion
• Matrix compression along isogenic blocks
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Beating the Optimal Verification of Entangled States via Collective Strategies