How can I find the best linear combination of a set of matrices to approximate a target matrix? 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!
 A: $\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.
A: 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 ! 
