2
$\begingroup$

I want to find $\theta$ such that

$ \theta = argmin_{\theta} \left( \left|\left| Y - \sum_{i=1}^k \theta_i X_i \right|\right| \right) $

where $X_i$ and $Y$ are N x N matrices and $\theta$ is a weight vector that specifies how to linearly combine the $k$ $X$'s to approximate Y.

This smells like a linear optimization problem though I'm unskilled in this kind of math and can't seem to formulate it as a linear program. I'd also be curious if anyone has any advice on how to learn this kind of math and/or problem formulation.

Thanks!

$\endgroup$
4
$\begingroup$

$\theta = argmin_{\theta} (Y - \sum_{i=1}^k \theta_i X_i)$ would be an affine function in $\theta$ and hence an unconstrained linear program.

But $\theta = argmin_{\theta} || Y - \sum_{i=1}^k \theta_i X_i ||$ has an arbitrary norm. Fortunately, norms are convex and convexity is preserved under compositions with affine functions, so the problem is simply an unconstrained convex optimization program. They can be solved easily. Here is an example from MATLAB using cvx.

Initialize 5 random normal 2x2 matrices and try to regress $Y$ on the 4 $X_i$'s in the Euclidean norm in this example (to change this, just use a different norm() function, of which cvx has many). If Y and the $X_i$'s are linearly independent, since there are only 4 degrees of freedom, we should be able to achieve 0 error, which we do.

N=2;
Y=randn(N,N);
X1=randn(N,N);
X2=randn(N,N);
X3=randn(N,N);
X4=randn(N,N);

cvx_begin
    variable theta(4);
    minimize(norm(Y-theta(1)*X1-theta(2)*X2-theta(3)*X3-theta(4)*X4))
cvx_end

Status: Solved

Optimal value (cvx_optval): +1.50457e-11

norm(Y)

ans = 1.3731

The norm of Y is about 1.4, and the norm of the difference given our thetas is effectively zero.

$\endgroup$
  • $\begingroup$ Does anyone know how LaTeX works here? I tried the faq here and also Google searching, but that of course leads to questions on tex.stackexchange.com/ $\endgroup$ – ncray Dec 2 '10 at 3:41
  • $\begingroup$ Okay I sort of got it working...but it's absurd how I have to keep doing the captchas due to my editing. Can I get around this short of not editing? $\endgroup$ – ncray Dec 2 '10 at 3:51
  • $\begingroup$ Wow. I am your biggest fan. That is so awesome. I got CVX, and moreover now have a couple hours of new homework to learn what the hell you did there. : ) $\endgroup$ – adam smith Dec 2 '10 at 4:28
3
$\begingroup$

If your norm is a hilbert space norm (for example root mean square error, also called hilbert schmidt norm in the case of matrices or l^2 norm if you take them as vectors) then obtaining the solution is a first year calculous exercise if you rephrase things using:

$c=(\langle Y,X_i \rangle)_{i=1,\dots,k}$ and $A=(\langle X_j,X_i \rangle)_{j,i=1,\dots,k}$ ($c$ is a vector and $A$ a $k\times k$ matrix).

The solution to your problem is given by solving $A\theta^*=c$ no need for optimization !

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.