compressed_solve

compressed_solve, a MATLAB 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.

MATLAB's backslash or "mldivide()" operator and its QR factorization solution approach seem to produce the same results as compressed_solve().

Licensing:

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

Languages:

compressed_solve is available in a MATLAB version.

Related Data and Programs:

compressed_solve_test

lawson, a Fortran90 code which contains routines for solving linear least squares (LLS) problems and singular value decompositions (SVD), by Charles Lawson, Richard Hanson.

llsq, a MATLAB 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 MATLAB code which computes the linear least squares (LLS) solution of a rectangular linear system A*x=b, using the QR factorization.

test_lls, a MATLAB code which implements linear least squares 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.m, returns a compressed solution of an underdetermined linear system.