MATLAB: Minimizing the values in an underdetermined Matrix – minimize with constraints

compressed sensingcompressive sensingconstraintsfminconMATLABmatrixminimize

I'm new to MATLAB, and there is probably a very simple way to do this. I have a linear set of equations Ax=b. I have matrix A and matrix b, and I need to solve for the smallest values in matrix x that satisfy the equation. The solution is underdetermined. Is there a way to do this? Essentially I need to minimize the components in the matrix x subject to constraints. Mathematica has the NMinimize function which looks perfect, except I cannot find an equivalent in MATLAB. fmincon does not seem to work for matrix entries.
Thanks

Best Answer

edit: fixed mistake in call to linprog
To perform L1 minimisation, you'll need access to an LP solver. If you have the optimization toolbox, linprog is your friend.
The easiest way to do it is as follows:
Define a vector t of the same length as x such that -t <= x <= t
The linear program is then
minimise    t(1) + ... + t(n)
subject to  A*x = b
            -x - t <= 0
             x - t <= 0
To solve it in MATLAB, I'll assume you have an m x n matrix A, and m x 1 vector b
[m, n] = size(A); 
f = [zeros(n, 1); ones(n, 1)];
Ai = [-eye(n), -eye(n); eye(n), -eye(n)];
bi = zeros(2*n, 1);
x = linprog(f, Ai, bi, [A, zeros(m, n)], b);
x = x(1:n);
Related Question