Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Design
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 $\mathbb{R}$, 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.
Code (1)
Tasks
Super-ResolutionTensor DecompositionSimilar Papers 제목 키워드 기반
Recovery of binary sparse signals from compressed linear measurements via polynomial optimization
The recovery of signals with finite-valued components from few linear measurements is a problem with widespread applications and interesting mathematical characteristics. In the compressed sensing framework, tailored met…
compressed sensingIterative Alpha Expansion for estimating gradient-sparse signals from linear measurements
We consider estimating a piecewise-constant image, or a gradient-sparse signal on a general graph, from noisy linear measurements. We propose and study an iterative algorithm to minimize a penalized least-squares objecti…
compressed sensingSupport Recovery in Universal One-bit Compressed Sensing
One-bit compressed sensing (1bCS) is an extreme-quantized signal acquisition method that has been intermittently studied in the past decade. In 1bCS, linear samples of a high dimensional signal are quantized to only one …
compressed sensingQuantizationImproved Support Recovery in Universal One-bit Compressed Sensing
One-bit compressed sensing (1bCS) is an extremely quantized signal acquisition method that has been proposed and studied rigorously in the past decade. In 1bCS, linear samples of a high dimensional signal are quantized t…
compressed sensingHyperparameter Optimization in Neural Networks via Structured Sparse Recovery
In this paper, we study two important problems in the automated design of neural networks -- Hyper-parameter Optimization (HPO), and Neural Architecture Search (NAS) -- through the lens of sparse recovery methods. In the…
Hyperparameter OptimizationNeural Architecture Search