A Variational Geometric Approach to Exact Recovery by $\ell_1/\ell_2$ Minimization

1 Introduction

• The existing ratio-model analyses do not generally determine whether a given signal is recovered, motivating pointwise local and global criteria.Local analysis must also account for feasible directions with zero directional derivative; global recovery requires comparisons across the feasible set.Source: §1 · p. 3
• The local and global pointwise criteria use directional and sublevel-set geometry to characterize recovery for the ℓ1/ℓ2 ratio objective.The analysis proceeds from pointwise characterizations to uniform sufficient conditions, rather than deriving those conditions solely through norm estimates and null-space inequalities.Source: §1 · p. 3
• For s ≥ 2, the sufficient uniform local condition uses coefficient c_s = max{1, (√s − 1)/2}, optimal within the considered scalar family for each fixed s.The condition depends only on the null space and sparsity order, and improves the compared coefficient (√s + 3)/2 [24, Corollary 3.3].Source: §1 · p. 3
• A positive margin in the local condition gives explicit growth moduli, localization radii, and thresholds for linear objective perturbations that leave the localized minimizer fixed.Uniform local recovery does not imply uniform global recovery.Source: §1 · p. 3
• The uniform global sufficient scalar bound has coefficient two, improving the compared coefficient three in [21, Theorem 4.1] and [24, Theorem 4.3].The coefficient is optimal within the considered scalar family when both sparsity order and dimension may vary.Source: §1 · p. 3

2 Variational Geometry of the Ratio Objective

• Directional behavior and sublevel-set geometry of Φ provide the geometric basis for the recovery conditions developed later.The section establishes notation and variational-analysis concepts used in that development.Source: §2 · p. 4

2.1 Characterizations of Critical Points

• At a reference signal, the directional derivative of Φ is continuous, convex, and positively homogeneous, and its local expansion has a quadratic-order remainder.When a direction has zero first derivative, the second-order behavior is strictly decreasing unless the direction is parallel to the signal; feasible nonzero directions cannot be parallel when b ≠ 0.Source: §2.1 · pp. 5–6
• Criticality is characterized equivalently by directional, null-space, and multiplier conditions.The affine constraint contributes the normal cone range(A⊤), while the directional criterion requires nonnegative directional derivative along feasible directions.Source: §2.1 · pp. 5, 7

2.2 Cone Geometry of C

• The radial cone to the reference sublevel set is characterized by Φ′(x∗; d) ≤ 0, while the global descent cone requires only one positive step with no larger objective value.The radial and global descent cones are positively scale invariant, but the global descent cone need not be convex or closed.Source: §2.2 · pp. 7–8
• For a direction not parallel to x∗, global descent can be tested using Φ(d) < Φ(x∗) or a comparison at a step where a support component becomes zero.At most |S| additional step comparisons are needed, one for each support index.Source: §2.2 · pp. 8, 10
• Closed symmetric outer estimates of the global descent cone yield sufficient recovery conditions; the support-dependent outer cone is used for the uniform condition.The estimates follow by projecting directions onto span{x∗}.Source: §2.2 · pp. 10–11

3.1 Local Exact Recovery and Stability

• Local exact recovery, first-order growth, strict positivity of every nonzero feasible directional derivative, and tilt stability are equivalent for the ratio objective.If the directional derivatives have a positive lower bound α on the unit sphere of ker(A), any 0 < κ < α is a local growth modulus on a sufficiently small neighborhood; small linear perturbations then leave the localized minimizer fixed.Source: §3.1 · pp. 12, 14, 15
• At most 2n linear-programming feasibility problems decide local exact recovery at a fixed signal, and the decision is polynomial-time when A and x∗ have rational entries.The test checks whether any nonzero feasible direction has nonpositive directional derivative.Source: §3.1 · p. 15
• At a critical point, either every nonzero feasible directional derivative is positive and the point is a local minimizer, or a zero-slope direction has negative curvature and rules out local minimality.If the critical point has full support and ker(A) is nontrivial, the second alternative implies strict local maximality.Source: §3.1 · p. 16

3.2 Global Exact Recovery

• Unique global recovery is equivalent to strict objective increase at every nonzero feasible displacement, or equivalently, no nonzero feasible direction belongs to the global descent cone.The global descent cone has an explicit characterization using coordinate-vanishing steps and an asymptotic comparison.Source: §3.2 · p. 17
• A null-space test characterizes global exact recovery by comparing Φ on each nonzero null-space direction and at no more than |S| feasible positive steps where a support coordinate vanishes.The comparisons at those steps are feasible because their measurements equal the nonzero data.Source: §3.2 · p. 17
• A scalar null-space bound involving the off-support ℓ1 norm is sufficient for exact recovery over the affine constraint set.The corollary also gives a specific sufficient bound for every nonzero null-space direction.Source: §3.2 · p. 18
• A descent-cone condition is sufficient, but not necessary, for both first-order growth and global exact recovery.The section states this using the descent cones associated with the objective.Source: §3.2 · p. 18
• Closing the descent cone can introduce a nonzero null-space direction even when first-order growth and global exact recovery both hold.This differs from affine-constrained nuclear-norm minimization, where the closed-cone condition is equivalent to first-order growth [11, Theorem 3.1].Source: §3.2 · p. 18
• Global exact recovery implies local exact recovery, but the converse can fail even at a sharp local minimizer.In the example, the signal is a sharp local minimizer but is not globally recovered, despite having a positive directional derivative along a direction in its descent cone.Source: §3.2 · p. 18

4.1 Uniform Local Exact Recovery

• For 2 ≤s ≤9, the sufficient local condition is precisely the ℓ1 null-space property of order s.The section also notes that for s = 1, uniform local recovery holds without a null-space assumption.Source: §4.1 · pp. 19–20
• A positive margin in the local null-space condition yields explicit growth moduli, localization radii, and bounds on linear perturbations.For normalized signals, the supplied passages give a common growth modulus and perturbation threshold; a common localization radius also requires a fixed positive lower bound on nonzero signal amplitudes.Source: §4.1 · pp. 20–21
• For each fixed s ≥2, the coefficient c_s in the local scalar condition is optimal across dimensions and measurement matrices.Reducing it can admit the condition even when a signal is not a local minimizer.Source: §4.1 · p. 22
• The local condition guarantees uniform local recovery, but it does not guarantee uniform global recovery.The section gives an example satisfying the local condition for s = 7 where global recovery fails.Source: §4.1 · p. 23

4.2 Uniform Global Exact Recovery

• A sufficient global null-space condition yields uniform global exact recovery for signals with at most s nonzeros and nonzero measurements.The scalar bound improves the compared coefficient from three to two.Source: §4.2 · pp. 23–24
• The global scalar coefficient two is optimal when both s and n may vary.For every c < 2, the section constructs a case satisfying the corresponding weaker bound without global minimization.Source: §4.2 · p. 24
• The sufficient global conditions are not necessary: an example has uniform global recovery even when the compared conditions fail.The text also states that uniform global recovery implies uniform local recovery, but not conversely.Source: §4.2 · pp. 24–25

• Necessary and sufficient conditions characterize local and global exact recovery in the affine-constrained ratio model with nonzero data.Source: Conclusions · p. 25
• Every local minimizer is sharp and tilt stable, and remains uniquely minimizing nearby under sufficiently small linear objective perturbations.Source: Conclusions · p. 25
• Uniform local exact recovery does not ensure uniform global exact recovery, which requires additional comparisons captured by the global descent cone.Source: Conclusions · p. 25
• Pointwise results yield improved sufficient null-space conditions for uniform recovery; their scalar coefficients are optimal within the stated local and global families.A positive margin in the local condition gives quantitative bounds on growth, localization, and admissible linear objective perturbations.Source: Conclusions · p. 25