Typical l₁-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices

DOI10.1088/1742-5468/2012/12/P12003MaRDI QIDQ3301307zbMATH OpenOpenAlexFDO

Authors Yoshiyuki Kabashima, Mikko Vehkaperä, Saikat Chatterjee

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52)

Abstract: We consider the problem of recovering an $N$-dimensional sparse vector $vmx$ from its linear transformation $vmy=vmDvmx$ of $M(<N)$ dimension. Minimizing the $l_1$-norm of $vmx$ under the constraint $vmy=vmDvmx$ is a standard approach for the recovery problem, and earlier studies report that the critical condition for typically successful $l_1$-recovery is universal over a variety of randomly constructed matrices $vmD$. For examining the extent of the universality, we focus on the case in which $vmD$ is provided by concatenating $b=N/M$ matrices $vm{O}_1,vm{O}_2,\mathrm{...},vm{O}_b$ drawn uniformly according to the Haar measure on the $MimesM$ orthogonal matrices. By using the replica method in conjunction with the development of an integral formula for handling the random orthogonal matrices, we show that the concatenated matrices can result in better recovery performance than what the universality predicts when the density of non-zero signals is not uniform among the $b$ matrix modules. The universal condition is reproduced for the special case of uniform non-zero signal densities. Extensive numerical experiments support the theoretical predictions.

Recommendations

• Nonuniform sparse recovery with subgaussian matrices
• Sparsity and incoherence in orthogonal matching pursuit
• Simple bounds for recovering low-complexity models
• On exact recovery of sparse vectors from linear measurements
• Stable signal recovery from incomplete and inaccurate measurements

Cites work

• scientific article; zbMATH DE number 1906319 (Why is no real title available?)
• A generalized uncertainty principle and sparse representation in pairs of bases
• Compressed sensing
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• Introduction to the replica theory of disordered statistical systems
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Perceptron capacity revisited: classification ability for correlated patterns
• Replica field theory for deterministic models. II. A non-random spin glass with glassy behaviour
• Sparse and redundant representations. From theory to applications in signal and image processing.
• The planar approximation. II
• Uncertainty principles and ideal atomic decomposition

Cited in

(6)

• Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction
• Analysis of sparse recovery algorithms via the replica method
• Bayesian signal reconstruction for 1-bit compressed sensing
• \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace
• On the Fundamental Limits of Recovering Tree Sparse Vectors From Noisy Linear Measurements
• Replica analysis of overfitting in generalized linear regression models

This page was built for publication: Typical \(l_1\)-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices

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