compressed_solve

compressed_solve, a Python code which handles an underdetermined linear system A*x=b, using a version of the QR factorization, and seeking a solution which has the fewest possible nonzero entries. This procedure is useful in the field of compressed sensing.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

compressed_solve is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

llsq, a Python code which solves the simple linear least squares (LLS) problem of finding the formula of a straight line y=a*x+b which minimizes the root-mean-square error to a set of N data points.

qr_solve, a Python code which computes the linear least squares (LLS) solution of a rectangular linear system A*x=b, using the QR factorization.

test_lls, a Python code which implements linear least squares (LLS) test problems of the form A*x=b.

Reference:

1. David Donoho,
   For most large underdetermined systems of linear equations, the minimal 1-norm solution is also the sparsest solution,
   Communications on Pure and Applied Mathematics,
   Volume 59, Number 6, 2006, pages 797-829.
2. Brian Hayes,
   The Best Bits,
   American Scientist,
   Volume 97, July-August 2009, pages 276-280.

Source Code:

• compressed_solve.py, the source code.
• compressed_solve.sh, runs all the tests.
• compressed_solve.txt, the output file.