Newton-Direction-Based ReLU-Thresholding Methods for Nonnegative Sparse Signal Recovery

1. Problem Statement

The paper addresses the Nonnegative Sparse Signal Recovery (NSSR) problem, a fundamental task in compressive sensing where the goal is to reconstruct a sparse signal $x \in \mathbb{R}^n$ from a small number of linear measurements $y \in \mathbb{R}^m$ ($m \ll n$), subject to the constraint that the signal entries must be nonnegative ($x \geq 0$).

The problem is formulated as:
$$y = Ax + e$$
where $A \in \mathbb{R}^{m \times n}$ is the measurement matrix and $e$ is noise. The recovery is modeled as an $\ell_0$-constrained optimization problem with nonnegativity:
$$\min_{x \in \mathbb{R}^n} \left\{ \frac{1}{2}\|y - Ax\|_2^2 : \|x\|_0 \leq k, x \geq 0 \right\}$$

Existing methods often struggle to balance the computational efficiency of Newton-type methods (which use second-order information) with the strict nonnegativity constraints required for this specific application.

2. Methodology

The authors propose two new algorithms that merge Newton-type search directions, ReLU (Rectified Linear Unit) thresholding, and hard thresholding.

Core Concepts

• Newton Direction: Uses the modified Hessian $(A^\top A + \varepsilon I)^{-1}$ to compute a search direction, offering faster convergence than first-order methods.
• ReLU Thresholding: Applies the function $\Psi(x) = \max(x, 0)$ to enforce nonnegativity before selecting the sparse support.
• Hard Thresholding: Selects the $k$ largest magnitude entries to enforce sparsity.

Proposed Algorithms

1. NDRT (Newton-Direction-Based ReLU-Thresholding):

   • Iterative scheme: $x^{(p+1)} = H_k(\Psi(u^{(p+1)}))$
   • Where $u^{(p+1)} = x^{(p)} + \lambda(A^\top A + \varepsilon I)^{-1}A^\top(y - Ax^{(p)})$.
   • This combines the Newton step, ReLU projection, and hard thresholding in a single step.

2. NDRTP (Newton-Direction-Based ReLU-Thresholding Pursuit):

   • An enhanced variant of NDRT.
   • After selecting the support set $S^{(p+1)}$ via ReLU and hard thresholding, it solves a Nonnegative Least Squares (NNLS) subproblem restricted to this support:
     $$x^{(p+1)} = \arg\min_{z} \left\{ \frac{1}{2}\|y - Az\|_2^2 : \text{supp}(z) \subseteq S^{(p+1)}, z \geq 0 \right\}$$
   • This "pursuit" step refines the coefficients, generally improving accuracy at the cost of slightly higher computation per iteration.

Parameter Selection

• Stepsize ($\lambda$): The authors derive a theoretical range for $\lambda$ based on the singular values of $A$. For practical implementation, they propose an empirical formula based on random matrix theory: $\lambda \approx (1 + \sqrt{n/m})^2$.
• Regularization ($\varepsilon$): A small positive constant to ensure the invertibility of the Hessian approximation.

3. Key Contributions

Theoretical Advancements

• Relaxed Regularization Condition: Previous Newton-based sparse recovery methods (e.g., NSIHT/NSHTP) required a restrictive condition $\varepsilon > \sigma_1^2$ (where $\sigma_1$ is the largest singular value of $A$). This paper proves that $\varepsilon$ can be an arbitrarily small positive number. This allows the matrix $(A^\top A + \varepsilon I)$ to be a true, slight perturbation of the Hessian, preserving the benefits of Newton's method.
• Convergence Guarantees: The authors establish sufficient conditions for exact recovery in noiseless settings and bounded error recovery in noisy settings. These conditions rely on the Restricted Isometry Property (RIP) constant $\delta_{3k}$ and the singular values of $A$.
  • For NDRT: Requires $\delta_{3k} + \sigma_1^2 - \sigma_m^2 < \frac{\sqrt{5}-1}{2} \approx 0.618$.
  • For NDRTP: Requires $\delta_{3k} + \sigma_1^2 - \sigma_m^2 < \frac{1}{\sqrt{3}} \approx 0.577$.
• Error Bound for Nonnegative Projection: A new fundamental error bound (Theorem 3.4) is established for the NNLS subproblem using Karush–Kuhn–Tucker (KKT) conditions, which is crucial for proving the convergence of NDRTP.

Algorithmic Improvements

• Integration of ReLU directly into the Newton iteration framework specifically for nonnegative constraints.
• Development of a practical, computationally cheap empirical formula for the stepsize $\lambda$, avoiding the need to compute singular values at every iteration.

4. Numerical Results

The authors conducted extensive experiments comparing NDRT and NDRTP against four state-of-the-art algorithms: RHT, RHTP, NNOMP, and NNSP.

• Setup:

  • Measurement matrix $A$: Gaussian entries ($N(0, 1/m)$).
  • Dimensions: $m=600, n=2000$.
  • Scenarios: Noiseless and noisy ($10^{-4}$ noise level).
  • Metrics: Success frequency (recovery rate) and CPU time.

• Findings:

  • Performance: NDRTP consistently outperformed all other methods, achieving the highest success frequencies at high sparsity levels. For example, at sparsity $k=310$ (noiseless), NDRTP achieved >90% success, while the next best (RHTP) dropped below 50%.
  • Robustness: NDRTP maintained superior performance in noisy environments, whereas NNOMP suffered significant degradation.
  • Efficiency: While NDRTP is slightly slower than simple thresholding methods (RHT/RHTP) due to the NNLS subproblem, it is faster than NNOMP and NNSP at higher sparsity levels.
  • Parameter Sensitivity: Experiments validated the empirical stepsize formula, showing optimal performance when $\lambda \approx 8$ (derived from $n/m$) and $\varepsilon \approx 0.5$.

5. Significance

This paper makes a significant contribution to the field of sparse signal recovery by:

1. Bridging Optimization and Deep Learning Concepts: It effectively utilizes the ReLU function (a staple of deep learning) within a classical iterative optimization framework to handle nonnegativity constraints naturally.
2. Overcoming Theoretical Limitations: By removing the restrictive $\varepsilon > \sigma_1^2$ condition, the proposed methods allow for more accurate Newton directions, theoretically enabling faster convergence and higher precision.
3. Practical Utility: The proposed NDRTP algorithm offers a robust, high-performance solution for applications where signals are inherently nonnegative and sparse, such as medical imaging, remote sensing, and face recognition, outperforming existing greedy and thresholding-based approaches.