Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Design

2022/04/16 by Daneshmand, Hadi, Bach, Francis
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2204.07879

Abstract

Mean field theory has provided theoretical insights into various algorithms by letting the problem size tend to infinity. We argue that the applications of mean-field theory go beyond theoretical insights as it can inspire the design of practical algorithms. Leveraging mean-field analyses in physics, we propose a novel algorithm for sparse measure recovery. For sparse measures over ℝ, we propose a polynomial-time recovery method from Fourier moments that improves upon convex relaxation methods in a specific parameter regime; then, we demonstrate the application of our results for the optimization of particular two-dimensional, single-layer neural networks in realizable settings.

Related

• On the Performance of Sparse Recovery via L_p-minimization (0<=p <=1)
• Optimal deep neural networks for sparse recovery via Laplace techniques
• Analysis of Sparse Recovery Algorithms via the Replica Method
• Recovery of Sparse 1-D Signals from the Magnitudes of their Fourier Transform
• Unified Theory for Recovery of Sparse Signals in a General Transform Domain