Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements

DOI10.1093/IMAIAI/IAW012zbMATH Open1386.94020arXiv1506.08159OpenAlexW2963890912MaRDI QIDQ4603729FDOQ4603729

Sohail Bahmani, Justin Romberg

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: 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 $mathcalW$ and a matrix $mathbfvarPsi$. 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 $mathcalW$ is a restricted isometry for low-rank matrices and $mathbfvarPsi$ 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.

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

Recommendations

• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Estimation of matrices with row sparsity
• Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Jointly low-rank and bisparse recovery: questions and partial answers

zbMATH Keywords

convex relaxationminimax ratehigh-dimensional estimationrestricted isometriessimultaneously low-rank and sparse matrices

Mathematics Subject Classification ID

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

Cites Work

• Templates for convex cone problems with applications to sparse signal recovery
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Exact matrix completion via convex optimization
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Estimation of high-dimensional low-rank matrices
• A simple proof of the restricted isometry property for random matrices
• Adaptive estimation of a quadratic functional by model selection.
• Sparse PCA: optimal rates and adaptive estimation
• Iterative hard thresholding for compressed sensing
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Sparse signal recovery from quadratic measurements via convex programming
• Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
• Robust Recovery of Signals From a Structured Union of Subspaces
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation

Cited In (8)

• Title not available (Why is that?)
• Sparse power factorization: balancing peakiness and sample complexity
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Jointly low-rank and bisparse recovery: Questions and partial answers
• Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
• Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling

Uses Software

• TFOCS
• SparsePR
• GESPAR
• PhaseLift
• Wirtinger Flow

This page was built for publication: Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements

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