Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Project: Recovering a Sparse Signal

Recover a sparse signal from far fewer measurements than unknowns using L1 minimization and FISTA. Compare with least squares, debias the result and map success against measurements.

In this project you solve a problem that looks impossible at first: recover a signal of 200 numbers from only 60 measurements. A system with more unknowns than equations has infinitely many solutions. The trick is an extra assumption: the true signal is sparse, meaning most of its entries are zero. Convex optimization with an L1 penalty can find it. This idea, called compressed sensing, is behind fast MRI scans and many signal-processing methods.

You will use tools from earlier lessons: the lasso, ISTA and FISTA and the prox of the L1 norm.

The setup

  • The unknown signal xโ‚€ โˆˆ โ„ยฒโฐโฐ has only k = 8 non-zero entries, at random positions with random values.
  • We take m = 60 measurements: b = A xโ‚€ + noise, where A is a random 60 ร— 200 matrix with independent Gaussian entries scaled by 1/โˆšm.
  • Goal: recover xโ‚€ from A and b.

Two candidate answers:

  1. Minimum-norm least squares: the solution of Ax = b with the smallest โ€–xโ€–โ‚‚. It is Aโบ b (pseudo-inverse), and it spreads energy over all entries: dense and wrong.
  2. The lasso: minimize ยฝโ€–Ax โˆ’ bโ€–ยฒ + ฮปโ€–xโ€–โ‚, solved with FISTA. Its L1 penalty drives most entries to zero.

Step 1: recover and compare

We choose ฮป small relative to the largest correlation, ฮป = 0.02 ยท โ€–Aแต€bโ€–_โˆž, which is a reasonable starting point for low noise. After FISTA, we also debias: refit ordinary least squares on only the entries the lasso selected, which removes the shrinkage caused by the L1 penalty.

Python Sparse recovery with FISTA

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The minimum-norm solution has all 200 entries non-zero and a relative error of about 0.86. The lasso finds all 8 true entries, plus a handful of small false ones (15 selected in this run), with an error of about 0.05. Debiasing cuts it to about 0.01, because the least-squares refit on 15 columns still explains the 60 measurements well and the false entries get tiny values.

Step 2: look at the picture

A figure makes the difference obvious. The plot compares the true signal with both reconstructions.

Python Plot the true and recovered signals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 3: how many measurements are enough?

Compressed sensing theory says that roughly m โ‰ˆ c ยท k ยท log(n/k) random measurements suffice, for a constant c of order 1 to 2. With n = 200 and k = 8, k log(n/k) โ‰ˆ 8 ยท 3.2 โ‰ˆ 26. The experiment below tests this: for each m we run 10 trials and count how often the support is recovered. We call a trial a success if the debiased relative error is below 5%.

Python Success rate versus number of measurements

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the run above, there were no successes at m = 15, 20 or 25, one at 30, six at 40 and all ten at 60. The exact counts depend on the random draws, but the sharp change from failure to success (a phase transition) is typical. Our strict 5% error test and the noise make the constant in m โ‰ˆ c ยท k log(n/k) land around 2 here.

Extensions to try

  • Change k (the number of non-zeros) and see how many measurements you need.
  • Increase the noise level to 0.1 and tune ฮป so the support is still right.
  • Replace the Gaussian A by a random 0/1 matrix and compare.
  • Instead of L1, try minimize โ€–xโ€–โ‚ subject to Ax = b (basis pursuit) using linprog with the split x = u โˆ’ v, u, v โ‰ฅ 0.

Why does L1 work and L2 not? The L1 ball has corners on the coordinate axes, so a flat set of solutions {x : Ax = b} tends to touch it at a sparse point. The L2 ball is round, and the touching point has no reason to be sparse.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is minimum-norm least squares a poor choice for recovering a sparse signal?

    The smallest L2 norm prefers many small entries over a few large ones, which is the opposite of sparsity.
  2. 2. What is the purpose of debiasing after the lasso?

    The lasso shrinks the kept coefficients toward zero; an unpenalized refit on the support fixes the amplitude.
  3. 3. Roughly how does the number of measurements needed scale with sparsity k and length n?

    Compressed sensing needs only a few multiples of k log(n/k) random measurements, far fewer than n.
  4. 4. What does a 'phase transition' mean in the success-rate experiment?

    Recovery success switches from rare to almost certain over a narrow range of m.

Summary

  • A sparse signal can be recovered from fewer measurements than unknowns by minimizing ยฝโ€–Ax โˆ’ bโ€–ยฒ + ฮปโ€–xโ€–โ‚.
  • FISTA solves the lasso with a few lines of code; debiasing refits the selected entries.
  • Minimum-norm least squares returns a dense, inaccurate answer.
  • Success depends sharply on m, roughly m โ‰ณ k log(n/k) times a small constant.

Next: Project: A Classifier from Scratch