Sparse Signal Recovery for Compressed Sensing

PhD Thesis Proposal Defence


Title: "Sparse Signal Recovery for Compressed Sensing"

by

Mr. Man Ting WONG


Abstract:

Compressed sensing concerns the reconstruction of high-dimensional signals
from far fewer linear measurements than their dimension, provided the signals
are sparse. Under random sensing designs satisfying the restricted isometry
property (RIP), convex formulations such as L1-regularized least squares
recover the unknown signal with high probability using k = O(s log(n/s))
measurements. Despite theoretical guarantees of recovery, practical
deployments still face challenges in solver efficiency and memory usage. In
fact, some modern solvers do not converge within minutes for n = 30,000 and
a moderate s.

We introduce Dynamic Working Set (DWS), a method for L1-regularized least
squares, min_x (1/2)||Ax − b||2 + η||x||1. It targets problems where the
true solution is sparse (s « n). DWS adaptively grows and shrinks the working
set based on how the current support reflects progress. The resulting working
set induces a smaller subproblem that is passed to a solver. As a result,
faster running times are obtainable because only a portion of the problem is
considered. We prove that for any ε > 0, DWS reaches a (1 + O(ε))-approximate
solution while each solver call and intermediate iterate remain provably
sparse, using only O((s/ε) log s log(η/ε)) variables when ε is known, or
O((k/ε) log k log(η/ε)) otherwise. In benchmarks, DWS is consistently faster
than GPSR, Celer, and Skglm, with speedups of up to about 3x. Compared with
Skglm, DWS converges faster to a working set and reduces overhead by keeping
the working set small.


Date:                   Friday, 31 October 2025

Time:                   10:00am - 12:00pm

Venue:                  Room 4472
                        Lifts 25/26

Committee Members:      Prof. Siu-Wing Cheng (Supervisor)
                        Prof. Ke Yi (Chairperson)
                        Dr. Sunil Arya