I have a linear equation system Q.m = t, with m unkown and where Q has dimensions {(n-1)²,n²}, t has dimensions {(n-1)²} and m dimensions {n²}. I'm trying to find a way to find a (possible) solution m1 such that Norm[Partition[m1,n]] is less or equal to 1. My idea goes something like this:

Somehow optimizing using the solution given by LinearSolve[Q,t] and NullSpace[Q]. I got some help with the code from a friend, he gave this suggestion:

ns = NullSpace[Q];
vars = Array[p, {Length@ns}];
sol = Partition[m + vars.ns, n];
NumericMatrixOnly[f_][args_?(MatrixQ[#, NumericQ] &)] := f[args]
res = FindMinimum[Max[NumericMatrixOnly[Norm][sol], 1], vars];]
m1 = sol /. Last@res;

This solution isn't as fast or accurate as I would want, in what other ways could I optimize this? I could do it with alternating projections, but I wanted to see if Mathematica have any nice built-in methods.

  • $\begingroup$ You can get a minimal l2 vector solution via m2 = LeastSquares[Q, t]. This might often suffice for your stated purpose. When it odes not it could give a good set of starting values for the FindMinimum approach. I suspect that latter has difficulty in that it is dealing with a matrix norm, for which it has no analytic expression for derivatives and the like. All the same, using a least-squares solution as a first guess should work well because there are inequalities relating that to Frobenius norm of the partitioned matrix, and that in turn to the 2-norm of that matrix. $\endgroup$ – Daniel Lichtblau Jun 11 '13 at 15:51

Your Answer

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

Browse other questions tagged or ask your own question.