Sparse Signal Recovery

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Sparse Signal Recovery"

By

Mr. Man Ting WONG


Abstract:

This thesis studies algorithmic aspects of compressed sensing and sparse 
recovery, with an emphasis on methods that scale to high-dimensional 
problems. It is based on two contributions, presented in Chapters 2 and 3, 
that address sparse reconstruction from different computational viewpoints.

In Chapter 2, we study how to speed up large-scale l1-regularized 
least-squares problems of the form: minimize (1/2)||Ax - b||^2 + eta
||x||1. This formulation is known to recover sparse signals under standard
random sensing designs. Although theory predicts accurate recovery from k =
O(s log(n/s)) measurements, practical use still faces challenges in solver
efficiency and memory usage, especially for problems with dimensions such as n =
30,000 and moderate sparsity. We introduce Dynamic Working Set (DWS), a method
that adaptively grows and shrinks a working set according to how the current
support reflects progress, and repeatedly solves smaller subproblems restricted
to that set. We prove that, for any epsilon > 0, DWS reaches a (1 +
O(epsilon))-approximate solution while each solver call and intermediate
iterate remain provably sparse. When epsilon is known, the method uses only
O((s/epsilon) log s log(eta/epsilon)) variables; otherwise it uses O((k/epsilon)
log k log(eta/epsilon)) variables. In benchmarks, DWS is consistently faster
than GPSR, Celer, and Skglm, with speedups of up to about 3x.

In Chapter 3, we take a different perspective and study recovery procedures 
that avoid iterative optimization entirely. Given compressed sensing 
measurements of an unknown vector z in R^n using random matrices, we present 
a simple method to determine z without solving any optimization problem or 
linear system. The method uses Theta(log n) random sensing matrices in R^(k x 
n) and runs in O(kn log n) time, where k = Theta(s log n) and s is the number 
of nonzero coordinates of z. We further adapt the method to determine the 
support of z and experimentally compare it with optimization-based approaches 
on binary signals.


Date:                   Tuesday, 5 May 2026

Time:                   10:00am - 12:00noon

Venue:                  Room 2132C
                        Lift 22

Chairman:               Dr. Terence Tsz Wai WONG (CBE)

Committee Members:      Prof. Siu-Wing CHENG (Supervisor)
                        Prof. Ke YI
                        Dr. Sunil ARYA
                        Prof. Min YAN (MATH)
                        Prof. Minming LI (CityU)