cs_recover
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false])
Input: A, y, method, sparsity, lambda, iters, tol, step, rho, debias · Output: result
What it is
Compressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y. method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros); the convex family fista, ista and bp need lambda= (named number, the penalty) instead. iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp; debias=true re-fits the recovered support by plain least squares afterwards.
Overloads
A can be vector or matrix; y can be vector or matrix; method can be string, number, or matrix; sparsity can be string, number, or matrix; lambda can be number or matrix; iters can be number or matrix; tol can be number or matrix; step can be number or matrix; rho can be number or matrix.
8 forms. Each carries its own inputs, outputs and worked example — pick the tab for the one you are calling.
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalTold the true sparsity k = 3 up front, OMP picks one column per iteration and stops the moment it has three — .iterations comes out equal to k, and the least-squares re-solve on that exact support drives the error to floating-point zero.lambda number, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionaliters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | — |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "omp", sparsity = 3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
3 iterations, converged true, error 3.19e-12
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixThe same A, x, and y, handed to FISTA instead — no sparsity= at all, the support falls out of the l1 penalty — takes hundreds of proximal-gradient steps rather than three, and still settles for an error around 1e-3 instead of machine precision, the shrinkage bias the next section is about.y vector or matrixThe same A, x, and y, handed to FISTA instead — no sparsity= at all, the support falls out of the l1 penalty — takes hundreds of proximal-gradient steps rather than three, and still settles for an error around 1e-3 instead of machine precision, the shrinkage bias the next section is about.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalThe same A, x, and y, handed to FISTA instead — no sparsity= at all, the support falls out of the l1 penalty — takes hundreds of proximal-gradient steps rather than three, and still settles for an error around 1e-3 instead of machine precision, the shrinkage bias the next section is about.lambda number, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionaliters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | — |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "fista", lambda = 1e-3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
563 iterations, converged true, error 1.75e-3
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.method matrix, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity matrix, optionalmethod (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).lambda matrix, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters matrix, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol matrix, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step matrix, optionaliters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.rho matrix, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias matrix, optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | Same problem, 2k-at-a-time candidate selection with pruning — converges in even fewer iterations than plain OMP here because the prune corrects for any early misstep, though OMP already had no misstep to correct on this well-conditioned a matrix. |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "cosamp", sparsity = 3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
2 iterations, converged true, error 4.87e-12
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalmethod (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).lambda number, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionaliters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | Subspace pursuit: the same structure as CoSaMP with a k-sized rather than 2k-sized working set each round — cheaper per iteration, same machine-precision result on this problem. |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "sp", sparsity = 3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
1 iterations, converged true, error 3.19e-12
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalmethod (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).lambda number, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionalNo least-squares solve at all — just a gradient step and a hard threshold to the k largest entries, repeated.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | Needs many more iterations than the solve-based greedy methods above to reach the same precision, the real cost of avoiding the solve. |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "iht", sparsity = 3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
35 iterations, converged true, error 5.91e-10
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalmethod (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).lambda number, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionalThe normalised variant of iht: the step size is recomputed from the gradient every iteration instead of held fixed, so it needs roughly a third as many iterations here and, unlike plain iht, cannot diverge from a poorly chosen fixed step.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | — |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "niht", sparsity = 3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
13 iterations, converged true, error 3.26e-10
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalmethod (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).lambda number, optionalthe convex family fista, ista and bp need lambda= (named number, the penalty) instead.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionaliters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | The same LASSO objective as fista, without the Nesterov momentum term. Both hit the iteration cap on this problem, but where fista still lands at a 1e-3-scale error, plain ista's slower O(1/t) convergence leaves it far short — the practical reason FISTA, not ISTA, is the default convex choice. |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "ista", lambda = 1e-3)
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
1000 iterations, converged false, error 1.58e0
| Code | Input | Output | Description |
result = cs_recover(A, y, [method="omp"], [sparsity=], [lambda=], [iters=200], [tol=1e-9], [step=], [rho=1.0], [debias=false]) | A vector or matrixCompressed-sensing reconstruction of a sparse vector x from an M×N sensing matrix A and a length-M measurement vector y.y vector or matrixBasis pursuit by ADMM: solves min ‖x‖₁ subject to Ax = y exactly rather than a penalized version of it — no lambda= to choose at all — landing between the greedy methods' machine precision and FISTA/ISTA's shrinkage bias, at a cost of roughly a hundred iterations on this problem.method string or number, optional (default "omp")method (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).sparsity string or number, optionalmethod (named string) selects the algorithm: the greedy family omp, cosamp, sp and iht/niht need sparsity= (named integer, the assumed number of non-zeros).lambda number, optionalBasis pursuit by ADMM: solves min ‖x‖₁ subject to Ax = y exactly rather than a penalized version of it — no lambda= to choose at all — landing between the greedy methods' machine precision and FISTA/ISTA's shrinkage bias, at a cost of roughly a hundred iterations on this problem.iters number, optional (default 200)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.tol number, optional (default 1e-9)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.step number, optionaliters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.rho number, optional (default 1.0)iters (named integer) caps the iteration count, tol (named number) the convergence tolerance, step (named number) the IHT step size, rho (named number) the ADMM penalty for bp.debias optional (default false)debias=true re-fits the recovered support by plain least squares afterwards. | result vector | — |
Examples
Written for this form and run by the build -- the output below is what the engine actually produced.
A = randn(60, 200, seed = 7) / sqrt(60)
x = zeros(200)
x[7] = 1.5
x[33] = -2.0
x[91] = 0.75
y = A * x
r = cs_recover(A, y, method = "bp")
print("{r.iterations} iterations, converged {r.converged}, error {norm(r.x - x):.2e}")
output
115 iterations, converged true, error 1.02e-8
How it works
nnls(A, b) — the x >= 0 least-squares solution, by Lawson-Hanson. A DRT's unknowns are resistances, and a negative resistance is not a slightly wrong answer but an impossible one; clipping an unconstrained fit at zero is a different estimate, because excluding a variable changes what the others should be. ── compressed sensing ────────────────────────────────── One dispatcher rather than eight builtins: the argument list is the same for all of them (A, y, and a sparsity or a penalty), and the choice of method is a keyword, so a script can compare methods by changing one word rather than one call. See qu_core::cs's module doc for how to choose.
From the note above this builtin in the interpreter, where the reasoning was written down as it was built.