compressed_solve

compressed_solve, an Octave 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.

Octave's backslash or "mldivide()" operator and its QR factorization solution approach DO NOT 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 and an Octave version.

Related Data and Programs:

compressed_solve_test

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

test_lls, an Octave 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.