Robust Sparse Signal Recovery with Outliers: A Hard Thresholding Pursuit Approach Based on LAD

This paper introduces the Graded Fast Hard Thresholding Pursuit (GFHTP$_1$) algorithm, which utilizes a quantile-truncated step size for LAD minimization to achieve exact sparse signal recovery from outlier-contaminated measurements without requiring prior knowledge of the signal's sparsity level.

The Gist

Imagine you are trying to solve a massive jigsaw puzzle. The picture you are trying to see is a Sparse Signal—a hidden image that is mostly empty space (black) with just a few important pieces (white) scattered around.

Now, imagine someone has thrown a handful of Outliers into the mix. These aren't just missing pieces; they are giant, glowing, neon-colored blocks that don't belong anywhere. They are huge, loud, and completely wrong. Your goal is to ignore these neon blocks and reconstruct the original picture using only the few real pieces.

This is the problem the paper tackles: How do we find the hidden signal when the data is full of massive, misleading errors?

Here is the breakdown of their solution, using everyday analogies:

1. The Old Way: The "Average" Approach (Least Squares)

Most traditional methods try to solve this by taking an "average" of all the data points.

• The Metaphor: Imagine you are trying to guess the average height of a group of people. If you have 100 people who are 5'6" and one giant who is 10 feet tall, the "average" will be skewed way up. The giant (the outlier) pulls the whole result off.
• The Problem: In math, this is called the Least Squares method. It treats every error equally. If one error is huge (like that 10-foot giant), the math panics and tries to adjust the whole picture to accommodate it, ruining the reconstruction.

2. The Paper's New Approach: The "Median" Strategy (LAD)

The authors switch to a method called Least Absolute Deviations (LAD).

• The Metaphor: Instead of calculating the average height, you line everyone up and pick the person right in the middle (the median).
• Why it works: If you have 100 people at 5'6" and one 10-foot giant, the person in the middle is still 5'6". The giant is ignored because they are too far out on the edge. LAD is "robust" because it doesn't care about the size of the outliers, only their existence. It effectively says, "I'm going to ignore the screaming neon blocks and focus on the quiet, consistent pattern."

3. The Missing Piece: The "Blind" Guess (Unknown Sparsity)

Here is the tricky part. To solve the puzzle, you usually need to know how many real pieces there are (the "sparsity").

• The Old Problem: Most algorithms are like a detective who says, "I can only solve this case if you tell me exactly how many clues there are." In the real world (like sensor networks or medical imaging), you often don't know this number.
• The Paper's Innovation: The authors created an algorithm called GFHTP1 (Graded Fast Hard Thresholding Pursuit).
  • The Metaphor: Instead of asking, "How many pieces are there?", this algorithm is like a detective who starts by looking for one clue. If they don't find the whole picture, they say, "Okay, let's look for two clues." Then three. Then four.
  • The "Graded" Step: It grows its search area slowly, like a plant growing leaves. It doesn't need you to tell it the final size of the plant; it just keeps growing until the picture looks right. This removes the need for "prior knowledge."

4. The Secret Sauce: The "Quantile Filter"

How does the algorithm know which neon blocks are the outliers and which are real signal?

• The Metaphor: Imagine you are sorting a bag of marbles by size. You decide to ignore the top 10% largest marbles because you suspect they are the "neon blocks" (outliers).
• The Mechanism: The algorithm uses a Quantile Truncation. It looks at all the errors (the difference between the guess and the data). It calculates a "cutoff line" (the median or a specific percentile). Anything bigger than that cutoff is treated as a "neon block" and ignored for the next step of the calculation. This keeps the math from getting distracted by the loudest noise.

5. The Result: Fast and Exact

The paper proves two amazing things:

1. Speed: It doesn't just work; it works fast. It can find the exact picture in a number of steps roughly equal to the number of real pieces.
2. Guarantee: They mathematically proved that if the "neon blocks" aren't too numerous (less than half the data), this method will always find the correct picture, even if you don't know how many pieces are in the puzzle to begin with.

Summary

In short, this paper introduces a new, smart detective (the GFHTP1 algorithm) that:

• Ignores the screaming giants (Outliers) by using a "median" strategy instead of an "average."
• Doesn't need you to tell it how many clues to look for (No sparsity prior).
• Grows its search area step-by-step (Graded approach).
• Filters out the noise using a "size limit" (Quantile truncation).

It's a robust, self-correcting way to see the signal through the noise, even when you don't know exactly what you're looking for.

Technical Summary

Here is a detailed technical summary of the paper "Robust Sparse Signal Recovery with Outliers: A Hard Thresholding Pursuit Approach Based on LAD" by Jiao Xu, Peng Li, and Bing Zheng.

1. Problem Statement

The paper addresses the fundamental challenge of sparse signal recovery in the presence of gross outliers.

• Model: Given a measurement matrix $A \in \mathbb{R}^{m \times n}$ (where $m \ll n$) and an observation vector $b$, the goal is to recover an $s$-sparse signal $x_0$ from:
  $$b = Ax_0 + \eta$$
  where $\eta$ represents an unknown outlier vector with a support set $T$ of cardinality $|T| = pm$ (where $p$ is the outlier ratio). The magnitudes of the outliers in $\eta$ can be arbitrarily large, significantly exceeding the signal components.
• Objective: Recover $x_0$ without prior knowledge of the sparsity level $s$.
• Formulation: The problem is modeled as a sparsity-constrained Least Absolute Deviations (LAD) minimization:
  $$\min_{x \in \mathbb{R}^n} \|b - Ax\|_1 \quad \text{s.t.} \quad \|x\|_0 \le s$$
  The $\ell_1$-norm is chosen over the traditional $\ell_2$-norm (Least Squares) because LAD is robust to impulsive noise and outliers, whereas LS is highly sensitive to them.

2. Methodology

The authors propose two iterative algorithms based on the Hard Thresholding Pursuit (HTP) framework, adapted for the non-smooth $\ell_1$-loss function.

A. Fast Hard Thresholding Pursuit (FHTP1)

• Mechanism: An alternating minimization scheme involving two steps per iteration:
  1. Candidate Support Identification: Updates the signal via subgradient descent followed by a hard thresholding operator $H_s$ (keeping the $s$ largest magnitude entries).
  2. Signal Refinement: Solves the sub-problem restricted to the identified support set using further subgradient descent.
• Step Size: Uses an adaptive step size based on the $\ell_1$-norm of the quantile-truncated residuals. Specifically, it truncates the largest residuals (potential outliers) using a quantile threshold $\theta_\tau$ before calculating the step size.
• Limitation: Requires prior knowledge of the sparsity level $s$.

B. Graded Fast Hard Thresholding Pursuit (GFHTP1)

• Innovation: Designed to eliminate the need for the sparsity prior $s$.
• Graded Strategy: Instead of fixing the support size to $s$, the algorithm grows the support size iteratively. At the $k$-th outer iteration, it seeks a $(k+1)$-sparse solution.
• Mechanism: Similar to FHTP1 but uses a graded hard thresholding operator $H_{k+1}$ (keeping the top $k+1$ elements) in the outer loop.
• Stopping Criterion: The algorithm stops when the support set stabilizes or the truncated residual norm falls below a threshold, ensuring exact recovery without knowing $s$ in advance.

C. Key Technical Components

• Quantile Truncation: The step size calculation relies on the $\tau$-quantile of the absolute residuals ($|b - Ax|$). By filtering out the top $(1-\tau)$ fraction of residuals (assumed to be outliers), the algorithm prevents large errors from corrupting the gradient update.
• Adaptive Step Size: The step size $\mu_k$ is derived theoretically to ensure convergence, depending only on the truncated residuals and not the unknown true signal.

3. Key Contributions

1. Parameter-Free Recovery: The GFHTP1 algorithm is the first efficient method to recover sparse signals from outlier-corrupted measurements without requiring prior knowledge of the sparsity level $s$.
2. Theoretical Guarantees:
   • General Sparse Signals: Established a linear convergence rate (error bound) under the Restricted Isometry Property for $\ell_1$ (RIP1).
   • Exact Recovery for "Flat" Signals: Proved that for signals where non-zero entries are of comparable magnitude (satisfying $x^*_1 \le \lambda x^*_s$), the algorithm achieves exact recovery ($x_s = x_0$) within at most $s$ iterations with high probability.
3. Novel Theoretical Tools:
   • Introduced a "Sandwich Inequality" for quantile-truncated residuals, providing rigorous upper and lower bounds essential for the convergence analysis.
   • Proved a key proposition showing that the estimated support set $S_k$ is a subset of the true support $S$ during the iterative process.
4. Practical Implementation: Designed a robust stopping criterion and a signal-independent step size rule, overcoming limitations of previous methods (like PSGD) that relied on signal-dependent parameters.

4. Experimental Results

The authors conducted extensive numerical experiments on synthetic and real-world data (MNIST images).

• Robustness: GFHTP1 and FHTP1 consistently outperformed state-of-the-art competitors (PSGD, AIHT, RLAD) in scenarios with high outlier ratios (up to 50%) and varying sparsity levels.
• Accuracy: Achieved exact recovery (Relative Error $\le 10^{-4}$) where other methods failed or degraded significantly.
• Efficiency: While GFHTP1 takes slightly more time than fixed-sparsity methods due to the search for $s$, it is significantly faster than competing robust methods and scales well.
• Real-World Application: In image restoration tasks (MNIST), the proposed algorithms successfully reconstructed images corrupted by gross outliers, achieving high Signal-to-Noise Ratios (SNR) compared to PSGD.

5. Significance

This work bridges a critical gap in compressive sensing and robust statistics:

• Practicality: It removes the unrealistic assumption that sparsity levels are known in real-world applications (e.g., sensor networks, face recognition).
• Robustness: It provides a mathematically rigorous framework for handling gross outliers (arbitrarily large errors), a scenario where traditional Least Squares and many existing sparse recovery algorithms fail.
• Theoretical Foundation: The establishment of convergence guarantees for LAD-based hard thresholding under RIP1 conditions advances the theoretical understanding of non-smooth optimization in sparse recovery.

In summary, the paper presents GFHTP1 as a superior, adaptive, and theoretically sound solution for recovering sparse signals from data heavily contaminated by outliers, offering both exact recovery guarantees and practical efficiency.