MATLAB: L2 norm minimization

mathematicsoptimization

Hello, I'd like to find a transformation of a set of vectors X that maps to known vectors Y. This can be expressed as a standard least square optimization problem, i.e min |WX – Y|^2 where W is the transformation matrix I'm looking for.

Additionally, I would like to minimize the L2 norm of the matrix W so the full minimization problem becomes : min |W|^2 + |WX – Y|^2

This problem can be solved with gradient descent and I was just wondering which function from the Matlab optimization tool I should use ?

Thanks!

Best Answer

Using an nonlinear optimizer to solve this is overkill and completely silly, when a linear solver does it for you. Besides, with an optimizer you need to worry about convergence issues, starting values, etc.

Append an identity matrix to X, in this case as extra columns of X. Also append zeros to y. Then use slash (i.e /) to solve the problem.

W = [Y,zeros(1,N)]/[X,eye(N)];

This solves the regularized problem, where N is the number of rows in X. This solves the problem you have, with no optimizer needed at all. See that when [X,ones(N)] has more columns than rows, it solves the least squares problem you are asking to solve.

doc slash
help slash

As an example,

For example, make up some data:

X = rand(10,20);
Y = rand(1,20);

We wish to solve the problem

W*X = Y

This is easily accomplished using slash, if we did no regularization at all.

u = Y/X
u =
   -0.10061    -0.039857    -0.087301      0.14731      0.40622      0.36113     -0.31992      0.32343     0.071708      0.16989

With regularization, thus solving the penalized sum of squares, we do it as:

u = [Y,zeros(1,10)]/[X,eye(10)]
u =
    -0.013147     0.042605    0.0085151     0.089504      0.24349       0.1602     -0.11616      0.20876      0.14126      0.13649

The solution has been biased towards zero, as we should expect.

Related Solutions

MATLAB: How to minimize the 12th norm of a difference vector

This is quite confusing, because you have not ever explained what you really want. In your words:

"x is a weighted sum of two vectores A and B, x= weight1 *A + weigth2*B. The purpose of the minimization is to find the weights that minimize x-y."

You say that you have vector y, and two vectors A and B. Then you need to compute the weighted linear combination x of vectors A and B, that minimizes the norm (lets not worry about which norm for the moment), so

norm(x-y) = norm((w1*A + w1*B) - y)

If you really want the 12norm here, this is a straight optimization problem, but the 12 norm is really not much different from the infinity norm. Solving an inf norm problem will reduce to a linear programming problem, whereas solving the 2-norm problem is simple linear least squares.

For example, to solve the 2-norm (i.e., Euclidean distance, which you did say above) problem, all you need do is:

W12 = [A(:),B(:)]\y(:);
weight1 = W12(1);
weight2 = W12(2);

That simple. So it is trivial to do. There are at least a half dozen other ways to compute the same set of weights in MATLAB, but the above solution is simplest. It yields a set of weights that minimize the 2-norm of the difference between x and y. There are no iterations needed. That is the true solution, IF you really wanted a 2-norm.

However, if you really wanted a 12 norm, and would not be interested in the infinity norm, then some iterative scheme would be employed.

Do you really need to do this as a 12 norm? Why would you pick such an arbitrary value as 12? As I said, it will be relatively little different from the infinity norm. For example:

v = randn(1,100);
norm(v,12)
ans =
        2.926
norm(v,inf)
ans =
        2.811

Whereas, the 2-norm is quite different.

norm(v,2)
ans =
       9.8925

So if you insist on computing the solution under a 12 norm via some (unspecified iterative scheme) I can show you some ways to do so. Will ANY reasonable iterative scheme suffice?

For example, lets make up some data, then I'll solve it under a 12-norm using fminsearch.

y = randn(100,1);
A = randn(100,1);
B = randn(100,1);

The 2 norm solution is:

W12_2norm = [A(:),B(:)]\y(:)
W12_2norm =
   -0.0024203
      0.11984

Now, create an objective function to use for an optimizer.

fun_12 = @(W12) norm((A*W12(1) + B*W12(2)) - y,12);
fun_12(W12_2norm)
ans =
       2.8766

The 2-norm solution is not the minimum set of weights for the 12norm problem. But it will provide starting values for the optimization.

[W12_12norm,fval] = fminsearch(fun_12,W12_2norm)
W12_12norm =
      0.31792
     -0.11325
fval =
       2.7072

So a different set of weights has been obtained, which yields a somewhat lower value for the 12-norm.

Again, the 12-norm seems a bit arbitrary to me. A different solution comes from the infinity norm.

fun_inf = @(W12) norm((A*W12(1) + B*W12(2)) - y,inf);
[W12_infnorm,fval] = fminsearch(fun_inf,W12_2norm)
W12_infnorm =
   -0.0047671
     -0.68259
fval =
       2.7561

I need to be a bit careful there, because the inf norm is really not well-solved using fminsearch, because the inf norm will not be a smooth, differentiable function. fminsearch would prefer differentiability. I'd have been better off using a linprog solution on that, but since you have not asked at all for an inf norm solution, I'm not going to go that deeply into the solution, especially since I have no idea what you really want.

If you can explain more clearly what you really need, I could give a more precise answer. And there are lots of iterative ways I could have solved this problem (fminbnd, for example), but I don't see why any particular iterative solution would be better than what I've shown already.

MATLAB: How can we minimize the maximum of absolute differences in matlab

https://de.mathworks.com/help/optim/ug/fminimax.html

Best wishes

Torsten.

Best Answer

Related Solutions

MATLAB: How to minimize the 12th norm of a difference vector

MATLAB: How can we minimize the maximum of absolute differences in matlab

Related Question