Compressive sensing

Recovery of a sparse vector from fewer random measurements than unknowns.

• True model: a vector with a few nonzero samples (spikes) at random locations.

• Operator: pylops.MatrixMult, a random Gaussian sensing matrix with unit-norm columns (drawn with a fixed seed).

• Data: the measurements, plus optional white Gaussian noise (noise_std, drawn with a fixed seed).

Solvers compared:

Solver	Formulation
LSQR	Damped least squares (no sparsity), solved with LSQR
ISTA	L1-regularized least squares (LASSO), solved with ISTA
FISTA	L1-regularized least squares (LASSO), solved with FISTA
AA-ISTA	L1-regularized least squares (LASSO), solved with Anderson-accelerated ISTA (PyProximal)
TwIST	L1-regularized least squares (LASSO), solved with the two-step iterative shrinkage/thresholding algorithm (PyProximal)
IRLS	Basis pursuit (L1 norm with exact data fit), solved with iteratively reweighted least squares
ADMM-BP	Basis pursuit, with the data fit as a projection onto an affine set, solved with ADMM (PyProximal)
PrimalDual-BPDN	Basis pursuit denoise (L1 norm with the data misfit bounded by the noise level), solved with the primal-dual algorithm (PyProximal)
OMP	Greedy L0 recovery with as many atoms as nonzero samples, solved with Orthogonal Matching Pursuit
IHT	L0-constrained least squares (as many nonzero samples as the true model), solved with accelerated Iterative Hard Thresholding (PyProximal)

The number of nonzero samples of the true model is given to the L0 solvers (OMP, IHT) and the noise level to PrimalDual-BPDN.

Source: benchmarks/compressive_sensing.

Results

Raw results: results/compressive_sensing.csv.

Sparse spikes

Sparse vector of n = 256 samples with k = 16 nonzero spikes at random locations (random signs, amplitudes between 1 and 2), measured by a random Gaussian matrix with m = 64 rows and unit-norm columns, plus white Gaussian noise.

Dataset parameters: k=16, m=64, n=256, noise_std=0.01, seed=0

Rank	Solver	MAE	PSNR [dB]	Time [s]	Figure
1	AA-ISTA	0.003175	51.24	0.269	view
2	TwIST	0.003175	51.24	0.047	view
3	FISTA	0.003082	51.00	0.014	view
4	ISTA	0.003141	50.85	0.104	view
5	PrimalDual-BPDN	0.003099	50.77	0.063	view
6	ADMM-BP	0.004241	50.11	0.087	view
7	IRLS	0.004862	48.95	0.249	view
8	IHT	0.06114	23.33	0.053	view
9	LSQR	0.198	21.22	0.001	view
10	OMP	0.09344	20.75	0.004	view