Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction

DOI10.1007/s10955-019-02292-6zbMath1416.62395arXiv1509.08995MaRDI QIDQ2316055

Mohammad Ramezanali, Anirvan M. Sengupta, Partha Pratim Mitra

Publication date: 26 July 2019

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

random matrices; phase transition; high-dimensional data; penalized regression; cavity method; compressed sensing

Mathematics Subject Classification ID

62H12: Estimation in multivariate analysis

62J07: Ridge regression; shrinkage estimators (Lasso)

62J05: Linear regression; mixed models

60B20: Random matrices (probabilistic aspects)

Uses Software

• CVXOPT
• PDCO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
• Statistical mechanics approach to 1-bit compressed sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Atomic Decomposition by Basis Pursuit
• Living on the edge: phase transitions in convex programs with random data
• The LASSO Risk for Gaussian Matrices
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Sparsity and incoherence in compressive sampling
• Regularization and Variable Selection Via the Elastic Net
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution