Basis Pursuit Denoising (BPDN)

BPDN formulates denoising as a convex optimization problem, guaranteeing a globally optimal solution without local minima traps. The objective function combines a quadratic data fidelity term (L2-norm squared error) with an L1-norm regularization penalty on the coefficient vector. This structure ensures computational tractability and repeatable results, unlike greedy algorithms such as Matching Pursuit that may converge to suboptimal local representations.

The L1-norm penalty is the mathematical engine driving sparsity in BPDN. Unlike L2 (ridge) regularization which shrinks coefficients but rarely sets them to zero, the L1-norm geometry—a diamond-shaped constraint region in high-dimensional space—forces coefficient vectors to intersect at axes, producing exact zeros. This property, rooted in compressed sensing theory, enables BPDN to select only the most salient dictionary atoms while discarding noise components, yielding interpretable sparse codes.

The hyperparameter λ (lambda) governs the trade-off between sparsity and fidelity:

• Large λ: Heavy penalty on L1-norm → fewer non-zero coefficients, aggressive denoising, risk of underfitting signal structure
• Small λ: Light penalty → more coefficients retained, better fit to noisy data, risk of overfitting
• λ → 0: Converges to ordinary least squares (no sparsity)
• λ → ∞: Converges to all-zero coefficient vector Optimal λ selection typically uses cross-validation or the L-curve criterion.

BPDN requires a dictionary matrix—a collection of prototype waveforms (atoms) that span the signal space. The algorithm decomposes the input signal into a sparse linear combination of these atoms. Dictionary choice critically impacts performance:

• Analytic dictionaries: DCT, wavelets, Gabor frames—mathematically defined with known properties
• Learned dictionaries: K-SVD, online dictionary learning—trained from data for domain-specific sparsity Overcomplete dictionaries (more atoms than signal dimensions) provide richer representational capacity.

BPDN achieves denoising through the principle that signal energy concentrates in few coefficients while noise energy spreads diffusely. By enforcing sparsity, the optimization retains the few large-magnitude coefficients representing true signal structure and discards the many small-magnitude coefficients dominated by noise. This is fundamentally different from linear filtering (e.g., low-pass) which attenuates frequency bands indiscriminately. BPDN preserves transient features, edges, and singularities that linear methods smear.

Several algorithmic approaches solve the BPDN convex program efficiently:

• Iterative Shrinkage-Thresholding (ISTA/FISTA): Proximal gradient methods with O(1/k²) convergence for FISTA
• Alternating Direction Method of Multipliers (ADMM): Splits problem into subproblems solved in parallel
• Least Angle Regression (LARS): Efficient homotopy method tracing the full regularization path
• Spectral Projected Gradient (SPGL1): Formulates as LASSO and solves via root-finding on the Pareto frontier Modern implementations leverage GPU acceleration for large-scale problems.

A greedy sparse approximation algorithm that iteratively decomposes a signal into a linear combination of waveforms, or atoms, selected from a redundant dictionary. Unlike BPDN's global L1 optimization, Matching Pursuit selects one atom at a time by projecting the residual onto the dictionary and choosing the atom with the maximum inner product. This makes it computationally lighter but potentially suboptimal compared to the convex relaxation approach of BPDN.

The mathematical engine behind BPDN's sparsity constraint. By penalizing the sum of absolute values of the coefficient vector, the L1-norm promotes solutions where most coefficients are exactly zero. This is the closest convex proxy to the combinatorial L0-norm. Key properties:

• Convexity: Guarantees a global minimum via standard optimization solvers
• Sparsity: Produces interpretable representations with few active atoms
• Robustness: Naturally suppresses noise while preserving sharp signal features

A signal processing paradigm proving that signals can be reconstructed from far fewer samples than the Nyquist rate requires, provided the signal is sparse in some transform domain. BPDN is the canonical recovery algorithm in compressed sensing, solving the convex optimization problem that reconstructs the original signal from undersampled measurements. The theoretical guarantees rest on the Restricted Isometry Property (RIP) of the measurement matrix.

A collection of elementary waveforms, or atoms, where the number of atoms exceeds the signal dimension. BPDN operates by selecting a sparse subset of these atoms to represent the signal. Dictionary design is critical:

• Analytical dictionaries: Wavelets, curvelets, Gabor atoms with known mathematical forms
• Learned dictionaries: Atoms optimized from training data via K-SVD or online dictionary learning
• Redundancy: Enables flexible, parsimonious representations of complex signal structures

The Least Absolute Shrinkage and Selection Operator is the statistical counterpart to BPDN. Formally identical in structure, LASSO minimizes a least-squares error term subject to an L1 constraint on the coefficient vector. The key distinction is context: LASSO originates in statistics for variable selection and prediction, while BPDN originates in signal processing for denoising and inverse problems. Both produce sparse solutions via the same convex optimization framework.

A deep convolutional architecture using fixed wavelet filters and a modulus non-linearity to extract translation-invariant, stable signal representations. Unlike BPDN's optimization-driven sparsity, scattering networks compute a deterministic time-frequency decomposition that is provably robust to local deformations. The connection lies in the shared use of wavelet dictionaries: scattering networks cascade wavelet transforms, while BPDN selects a sparse subset of wavelet atoms via optimization.