REVIEW 6 cited by
Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal $f \in \C^N$ and a randomly chosen set of frequencies $\Omega$ of mean size $\tau N$. Is it possible to reconstruct $f$ from the partial knowledge of its Fourier coefficients on the set $\Omega$? A typical result of this paper is as follows: for each $M > 0$, suppose that $f$ obeys $$ # \{t, f(t) \neq 0 \} \le \alpha(M) \cdot (\log N)^{-1} \cdot # \Omega, $$ then with probability at least $1-O(N^{-M})$, $f$ can be reconstructed exactly as the solution to the $\ell_1$ minimization problem $$ \min_g \sum_{t = 0}^{N-1} |g(t)|, \quad \text{s.t.} \hat g(\omega) = \hat f(\omega) \text{for all} \omega \in \Omega. $$ In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for $\alpha$ which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp. The methodology extends to a variety of other setups and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one or two-dimensional) object from incomplete frequency samples--provided that the number of jumps (discontinuities) obeys the condition above--by minimizing other convex functionals such as the total-variation of $f$.
Forward citations
Cited by 6 Pith papers
-
Sparse Gradient Compression for Fine-Tuning Large Language Models
SGC compresses LLM optimizer states into a low-dimensional subspace via top-k gradient sparsification and OMP recovery, claiming comparable fine-tuning accuracy with fewer optimizer states.
-
Joint phase reconstruction and magnitude segmentation from velocity-encoded MRI data
A joint variational model with non-convex Bregman iteration reconstructs magnitude, velocity phase, and segmentation from undersampled velocity-encoded MRI, outperforming a sequential baseline on synthetic and real bu...
-
Sparse Representation Based Efficient Radiation Symmetry Analysis Method for Cylindrical Model of Inertial Confinement Fusion
A compressed-sensing method with geometry-adapted polynomial bases solves the ICF radiation view-factor model from about one tenth of the equations, cutting computation time by up to 80x on Shenguang II and III models.
-
Re-Weighted $\ell_1$ Algorithms within the Lagrange Duality Framework: Bringing Interpretability to Weights
A duality-based weight update rule for re-weighted L1 and LASSO algorithms that interprets weights as Lagrange multipliers with comparable empirical performance.
-
A Bayesian Lasso based Sparse Learning Model
A sparse Bayesian learning method whose weight prior is scaled by the noise variance, yielding a noise-dependent pruning threshold and improved noise variance estimates.
-
Rethinking Transformer Connectivity: TLinFormer, A Path to Exact, Full Context-Aware Linear Attention
TLinFormer compresses long history into a fixed-size context state to make each full forward pass linear in sequence length, but the attention is not exact and per-token generation still costs O(N).
Discussion (0). Continue with ORCID to comment.