A Unified Framework for Sparse Relaxed Regularized Regression: SR3

Motivation

• Sparse regression remains difficult because practical performance can require restrictive theory, fast solvers are lacking for large ill-conditioned problems, nonconvex methods are challenging, and data may need high fidelity.Source: §I · p. 1

Contributions

• SR3 is reported to improve computational efficiency, accuracy, convergence rates, and flexibility across compressed sensing, LASSO, matrix completion, total variation, and group sparsity.Source: §I · pp. 1–2

SR3 formulation

• SR3 introduces an auxiliary variable w constrained to remain close to Cx, allowing sparsity and accuracy requirements to be split between w and x.The relaxation parameter κ controls both the gap between Cx and w and the trade-off between improved geometry and fidelity to the original problem.Source: §II · p. 2

Generality

• The relaxed framework applies to convex and nonconvex regularizers, including ℓ1, ℓp with p < 1, SCAD, compressed sensing, and total variation.The formulation also covers linear composite regularizers through the choice of C.Source: §II · p. 2

Value-function geometry

• Partial minimization in x yields a problem in w with nearly spherical level sets, making support identification easier than with the elongated ellipses of the original least-squares geometry.For square orthogonal C, the transformed map Fκ shrinks singular values with less shrinkage for smaller ones, reducing the condition number.Source: §II · p. 2, A. SR3 and Value Function Optimization · pp. 2–3

Theory

• When λ = 0, SR3 and the original formulation share the same solution set, while the relaxed problem can have substantially better conditioning under appropriate assumptions on C.For square orthogonal C, choosing κ as described gives cond(Fκ) ≤ 1 + cond(A)/µ.Source: A. SR3 and Value Function Optimization · pp. 2–3

Algorithmic formulation

• SR3 applies proximal-gradient updates to the relaxed problem, using the prox of R(w) rather than a composed regularizer.This avoids the potentially difficult iterative prox evaluation required for the original formulation when C ≠ I.Source: B. Algorithms for the SR3 Problem · pp. 3–4

Convergence

• SR3 converges at a sublinear rate to a stationary point of its regularized least-squares objective.The stated theorem applies to SR3's value function, including settings where R may be nonsmooth and nonconvex.Source: B. Algorithms for the SR3 Problem · p. 4
• SR3 convergence rates depend less on A than the corresponding original-problem rates, including independence from A when A is rank-deficient.For full-rank A, the dependence is characterized as weak in the cited theorem.Source: B. Algorithms for the SR3 Problem · p. 4

Conditioning and trade-offs

• When C^⊤C = I and n > d, SR3 remains implementable with rates given by a separate corollary, although the comparison algorithm may not be implementable.The stated limitation concerns the original comparison algorithm, not SR3 itself.Source: B. Algorithms for the SR3 Problem · p. 4

Algorithmic formulation

• The SR3 algorithm supports both convex and nonconvex regularizers whenever their proximal operators are available.Examples include soft-thresholding for the ℓ1 norm and several nonconvex proximal operators.Source: B. Algorithms for the SR3 Problem · pp. 3, 5

Nonconvex regularizers

• The ℓ0 regularizer counts nonzero entries and uses hard thresholding as its proximal operator in SR3.This replaces the soft-thresholding operator used for the ℓ1 regularizer in the algorithm.Source: 1) Nonconvex Regularizers · p. 5

Nonconvex regularizers

• For 0 < p < 1, the ℓp regularizer promotes sparsity through a nonconvex proximal subproblem that can be solved globally coordinatewise.A provably convergent Newton method is available for all p, and ℓ1/2 is reported as particularly important for compressed sensing.Source: 2) Nonconvex Regularizers · p. 5
• The clipped absolute deviation regularizer reduces bias, and its combination with SR3 obtains the best compressed-sensing results reported in the paper.The cited passage refers to the un-smoothed CAD form and its analytic proximal operator.Source: 3) Nonconvex Regularizers: (S)CAD · p. 5

Applications

• In total variation, SR3 handles TV(x) = R(Cx) = ∥Cx∥1 with a primal proximal-gradient method rather than the primal-dual methods commonly used for the composition.The difference matrix C supplies the analysis operator in the TV formulation.Source: 4) Composite Regularization: Total… · p. 5

Constraints

• SR3 supports projection-based constraints, including convex non-negativity and nonconvex spherical constraints.These constraints are represented by indicator-function regularizers whose proximal operators are projections.Source: 5) Constraints as Infinite-Valued… · p. 5

Relaxation trade-off

• As κ increases, the relaxed solution moves closer to optimality for the original problem, while smaller κ values make the relaxed problem easier to solve.Moderate κ values produce useful solutions across applications according to the paper's practical observation.Source: D. Optimality of SR3 Solutions · p. 5

Applications

• SR3 is applied to variable selection, compressed sensing, total-variation denoising, and matrix completion, with support identification emphasized for noisy or ill-conditioned data.The LASSO experiments use noisy observations, and the paper reports improved support usefulness in that setting.Source: §III · pp. 5–6, A. SR3 vs. LASSO and Compressed Sensing · p. 6

LASSO path

• SR3 recovers the support without false positives across the LASSO path until overfitting begins at the 201st nonzero entry.LASSO makes mistakes early along the path, whereas SR3 maintains support recovery throughout the stated range.Source: 1) LASSO Path · p. 7

Noise robustness

• SR3 achieves a uniformly higher F1-score than LASSO across the tested noise levels.The comparison uses 200 random trials over noise levels σ ∈ {0.2i : i = 0, 1, ..., 20}.Source: 2) Robustness to Noise · p. 7

Computational efficiency

• SR3 requires far fewer iterations than ADMM and proximal gradient methods while retaining nearly identical per-iteration complexity.ADMM and SR3 require one-time formation and factorization of an n × n matrix, unlike IRucLq-v, which repeats matrix formation and inversion each iteration.Source: 3) Computational Efficiency · p. 7, Table II · p. 7

Compressed sensing

• For coherent uniform measurements, SR3 recovery is only slightly degraded and is the only approach with perfect recovery at m/k ≤ 10.The perfect-recovery formulations are SR3-CAD, SR3-ℓ1/2, and SR3-ℓ0.Source: 4) SR3 for Compressed Sensing · p. 8

Analysis versus synthesis

• SR3 directly extracts sparse analysis coefficients through w, whereas standard analysis requires post-processing because Cx is not completely sparse.In the reported comparison, w captures the true support cleanly while Cx requires thresholding for a support estimate.Source: 5) Analysis vs. Synthesis · pp. 8–9

Total variation regularization

• For total variation deblurring, FISTA acceleration makes SR3 converge much more rapidly to the minimum loss, although unaccelerated SR3 has comparable SNR to standard TV.The reported SNRs are approximately 26.10 for SR3 and 26.03 for standard TV, with variation depending on parameter choice and iteration limits.Source: B. SR3 for Total Variation… · p. 10

Visualization

• Figure 9 compares recovered signals against the true signal in its first row and estimated derivatives against true magnitudes in its second row.The columns correspond to ℓ0 and ℓ1 regularization.Source: Figure 9 · p. 11

Derivative recovery

• SR3 TV regularization uses a forward-difference map so the auxiliary variable w estimates the signal’s discrete derivative.The recovered signals and derivative estimates are compared for ℓ0 and ℓ1 regularizers.Source: C. SR3 for Exact Derivatives · p. 11, Figure 9 · p. 11
• Both ℓ0 and ℓ1 reasonably identify derivative-support groups, enabling accurate piecewise-constant signal recovery after grouping.The grouping procedure averages x over contiguous indices where w_i = 0.Source: C. SR3 for Exact Derivatives · p. 11

Regularizer comparison

• ℓ0-TV gives a less biased derivative-magnitude estimate than ℓ1-TV, producing a more faithful signal after integration.This generic inversion avoids relying on an explicit step-function assumption.Source: C. SR3 for Exact Derivatives · p. 11

Problem setup

• The seismic interpolation task addresses missing-data artifacts caused by subsampled sources and receivers in computationally expensive acquisition settings.The method targets simultaneous signal sampling and compression for seismic applications.Source: D. SR3 for Matrix Completion · p. 12

SR3 formulation

• SR3 relaxes the classic rank-penalty formulation and alternates least-squares updates for X with singular-value thresholding for W.The recovered interpolation is evaluated using X rather than the auxiliary W.Source: D. SR3 for Matrix Completion · p. 12

Problem setup

• 85% of the data is missing in the frequency-slice experiment, which is transformed to the midpoint-offset domain before interpolation.The slice is arranged as a 401×401 matrix and transformed back for comparison.Source: D. SR3 for Matrix Completion · p. 12

Results

• SR3 fits the original data better than the classic formulation, reaching a maximum SNR of 12.6.The comparison uses SNR because image quality is difficult to assess visually.Source: D. SR3 for Matrix Completion · p. 12
• ℓ0 formulations achieve better data fitting at a given rank than ℓ1 formulations, while SR3 Pareto curves lie below the corresponding classic curves.Lower Pareto curves indicate lower observed-data misfit for the same rank.Source: D. SR3 for Matrix Completion · p. 12

Problem setup

• Group sparsity regularizes multiple underdetermined learning tasks by encouraging redundancy among their solution vectors.The formulation assumes that some systems may share the same solution vector.Source: E. SR3 for Group Sparsity · p. 12
• The original group-sparsity objective is difficult because the composed ℓ2 penalty is nonsmooth and lacks an efficient proximal operation.Pairwise differences are represented through a linear mapping D.Source: E. SR3 for Group Sparsity · p. 12

SR3 formulation

• SR3 introduces auxiliary variables w_ij to approximate the pairwise differences D_ijx.This relaxation separates the composite penalty from the primary variables.Source: E. SR3 for Group Sparsity · p. 12

Experiment

• With n = 200, m_i = 150, k = 7, Gaussian sensing matrices, and noise level σ = 0.1, the experiment tests recovery of predefined groups.The problem uses underdetermined random linear systems.Source: E. SR3 for Group Sparsity · p. 12

Results

• 47% relative error from the direct SR3 solution falls to 1% after regrouping least-squares problems using the pattern discovered by w.The 1% error is described as essentially optimal given the noise.Source: E. SR3 for Group Sparsity · p. 13

Discussion

• The paper presents SR3 as a broadly applicable architecture satisfying robustness, computational-efficiency, and generalizability goals for sparse regression.The discussion also identifies automatic parameter tuning as future work.Source: §IV · pp. 13–14

Optimization preliminaries

• For nonconvex objectives, stationarity is necessary but not sufficient for global optimality, so iterative methods target stationary points.Distance to stationarity is used to detect convergence and analyze algorithms.Source: Subdifferential and Optimality · p. 14

Moreau envelope

• The Moreau envelope smooths proper closed convex functions, but it may remain nonsmooth when the underlying function is nonconvex.The ℓ0 example illustrates this nonconvex limitation.Source: Moreau Envolope and Prox Operators · p. 14, Figure 14 · p. 15

Proximal operators

• The ℓ1 proximal operator is element-wise soft-thresholding, whereas the ℓ0 proximal operator is element-wise hard-thresholding.These operators enable SR3 updates for common sparse regularizers.Source: Common Prox Operators · pp. 14–15
• The ℓ2-squared proximal operator scales the input vector, while the ℓ2 norm promotes group sparsity and does not decouple into scalar problems.The ℓ2 norm nevertheless has a closed-form solution.Source: Common Prox Operators · p. 15

Algorithms

• Proximal gradient descent alternates a gradient step on the smooth term with a proximal update for the nonsmooth term.The appendix gives the iteration x^k = prox_ηg(x^(k−1) − η∇f(x^(k−1))).Source: Common Prox Operators · p. 16

• Proximal gradient descent is presented for objectives of the form p(x) = f(x) + g(x).Source: Proximal Gradient Descent · p. 16
• The theorem assumes that p and g are closed convex functions and defines optimal values and solutions.Source: Proximal Gradient Descent · p. 16
• When ∇f is β-Lipschitz continuous, the prescribed step size is 1/β.Source: Proximal Gradient Descent · p. 16
• The section identifies these convergence results as well known in the proximal-gradient literature.Source: Proximal Gradient Descent · p. 16

• The analysis derives an explicit SR3 formulation in the relaxed coordinates w alone.Source: THEORETICAL RESULTS · p. 16
• The w-only problem has greatly improved conditioning compared with the original regression problem.Source: THEORETICAL RESULTS · p. 16
• The theory also obtains a quantitative measure of the distance between solutions of the original problem and the SR3 relaxation.Source: THEORETICAL RESULTS · p. 16
• The analysis uses singular-value decompositions of A and C to characterize spectral properties of the relaxed problem.Source: 1) Proof of Theorem 1 · p. 16
• The condition-number expression depends on σmin(A⊤A), σmax(C⊤C), and the relaxation parameter κ.Source: 1) Proof of Theorem 1 · p. 16

• The proof analyzes the iterates generated by the proximal gradient method.Source: 2) Proof of Theorem 2 · p. 17
• It combines the iterates with a first-order optimality condition to derive the needed inequality.Source: 2) Proof of Theorem 2 · p. 17
• After summing and simplifying the inequalities, the proof obtains the desired convergence result.Source: 2) Proof of Theorem 2 · p. 17
• The result is obtained by combining Theorem 2 and Theorem 1.Source: 3) Proof of Theorem 3 · p. 17

4) Proof of Corollary 2.:

• The solution-comparison analysis fixes κ as a constant and sets C = I.Source: Characterizing Optimal Solutions of SR3 · p. 17
• The proof uses optimality conditions and subgradient sets for the original and relaxed problems.Source: Characterizing Optimal Solutions of SR3 · p. 17
• When A⊤A = I, the relaxed solution is a stationary point of the original problem.Source: 5) Proof of Theorem 4 · p. 17
• When AA⊤ = I, the distance from zero to the relevant subgradient set is bounded by 1/(1 + 2κ).Source: 5) Proof of Theorem 4 · p. 17
• The implementation analyzes derivatives and uses Newton's method to locate a local minimum before comparing it with the value at zero.Source: A. Implementation of ℓq proximal… · p. 18