A Variational Geometric Approach to Exact Recovery by ℓ1/ℓ2 Minimization
Abstract
For affine-constrained ℓ1/ℓ2 minimization with nonzero data, a variational geometric approach is developed to characterize exact recovery. Necessary and sufficient conditions for local and global exact recovery are established in terms of directional derivatives and cones associated with sublevel sets of the ratio objective. The local analysis further reveals that local minimality, first-order growth, and tilt stability are equivalent. These pointwise characterizations lead to improved sufficient conditions for uniform recovery of sparse signals. The sufficient condition for uniform local recovery has coefficient cs=max{1,(√s−1)/2} for s≥2. For each fixed s, the coefficient cs is optimal within the considered family of local null-space conditions. Projection estimates yield a scalar bound for uniform global recovery with coefficient two, improving the earlier coefficient three. The coefficient two is optimal within the considered family of global null-space bounds when both s and n may vary. A positive margin in the local null-space condition provides explicit growth moduli, localization radii, and bounds on linear objective perturbations that leave the localized minimizer fixed. Examples show that uniform local recovery does not imply uniform global recovery.
Related
- Stochastic Geometrically Exact Beams: Continuous-Time Geometric Principles and Variational Discretizations
- Discretization-free exact recovery in geometric community detection
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry
- KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering
BibTeX
@misc{liu2026variational,
title = {{A Variational Geometric Approach to Exact Recovery by $\ell_1/\ell_2$ Minimization}},
author = {Yulan Liu and Rongrong Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34842},
eprint = {2610.34842},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34842},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A Variational Geometric Approach to Exact Recovery by ℓ_1/ℓ_2 Minimization
AU - Yulan Liu
AU - Rongrong Lin
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34842
UR - https://arxiv.org/abs/2610.34842
AB - For affine-constrained ℓ_1/ℓ_2 minimization with nonzero data, a variational geometric approach is developed to characterize exact recovery. Necessary and sufficient conditions for local and global exact recovery are established in terms of directional derivatives and cones associated with sublevel sets of the ratio objective. The local analysis further reveals that local minimality, first-order growth, and tilt stability are equivalent. These pointwise characterizations lead to improved sufficient conditions for uniform recovery of sparse signals. The sufficient condition for uniform local recovery has coefficient c_s=max{1,(√s−1)/2} for s≥2. For each fixed s, the coefficient c_s is optimal within the considered family of local null-space conditions. Projection estimates yield a scalar bound for uniform global recovery with coefficient two, improving the earlier coefficient three. The coefficient two is optimal within the considered family of global null-space bounds when both s and n may vary. A positive margin in the local null-space condition provides explicit growth moduli, localization radii, and bounds on linear objective perturbations that leave the localized minimizer fixed. Examples show that uniform local recovery does not imply uniform global recovery.
ER -