Least square given constraint on subcomponents - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T17:27:26Z http://mathoverflow.net/feeds/question/47025 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47025/least-square-given-constraint-on-subcomponents Least square given constraint on subcomponents Kenny 2010-11-23T00:22:38Z 2010-11-29T19:50:39Z <p>Hi all,</p> <p>I have to find a set of parameters that fit to a set of data with constraint to a subset of the parameters. In summary, I want to solve $\min ||A[x_1 \, x_2]^T -b ||$ given $||x_2|| = g$.</p> <p>I thought the problem is trivial but it turns out that it is not trivial at all. Lagrange multiplier approach gives a very complicated matrix equation (still not solvable for me). Any idea, or numerical/analytical solution, is greatly appreciated.</p> <p>Thanks.</p> http://mathoverflow.net/questions/47025/least-square-given-constraint-on-subcomponents/47040#47040 Answer by Mike Spivey for Least square given constraint on subcomponents Mike Spivey 2010-11-23T02:07:29Z 2010-11-23T02:07:29Z <p>You can express this problem as a <a href="http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program" rel="nofollow">quadratically constrained quadratic program</a> (QCQP). Unfortunately, because of the equality constraint, the QCQP will be nonconvex. However, there is some discussion on the Wikipedia page for handling nonconvex QCQP's, and a Google search should turn up more. This paper "<a href="http://www.stanford.edu/class/ee392o/relaxations.pdf" rel="nofollow">Relaxations and Randomized Methods for Nonconvex QCQP's</a>" might help, too; Example 1.2.1 in the paper is very similar to your problem.</p> http://mathoverflow.net/questions/47025/least-square-given-constraint-on-subcomponents/47073#47073 Answer by robin girard for Least square given constraint on subcomponents robin girard 2010-11-23T08:49:07Z 2010-11-23T11:53:17Z <p>Have you tryed a simple newton algorithm (with the constraint added to the algo)? </p> <p>Let $(\alpha_{k})$ be defined as: $\alpha_k=1/k^2$ </p> <blockquote> <p><strong>Initialisation</strong> : </p> <p>$x^0=[0,...,0]$</p> <p>Compute $H=(A^* A)^{-1}$</p> <p><strong>Loop for</strong> $k$ in $1:m$</p> <p>$x^k=x^{k-1}-\alpha_k H A^*(Ax^{k-1}-b)$</p> <p>$x^{k}=g*x^{k}/\|x_2^k\|$</p> <p><strong>end for loop</strong></p> </blockquote> <p>Obviously, there are more adaptive way of choosing $\alpha_k$... but maybe you don't need such sofistication to solve a norm minimization problem. If $A^* A$ has very small eigen values you can use $H_k=(A^* A+\epsilon_k)^{-1}$ instead of $H$ ($\epsilon_k$ decreasing to zero)...</p> <p>Note that this type of code is relatively general when you want to find the saddle point of a lagrangian and you know how to find the maxima with respect to Lagrange multipliers (in the dual space) (second step of the loop) but you need a gradient descent (or here Newton algo) for finding the minima in the principal space. </p> <p>Here is the corresponding R code: </p> <pre><code>A=t(array(1:1000,c(10,100))) m=100; b=1:10; g=3; l=5; p=10; alpha=1:m alpha=1/alpha^2 x=array(0,c(m,p)) H=t(A)%*%A svdH=svd(H) H=svdH$v%*%diag(1/svdH$d)%*%t(svdH$u) for (k in 2:m) { x[k,]=x[k-1,]-alpha[k]*H%*%(t(A)%*%(A%*%x[k-1,]-b)) x[k,]=g*x[k,]/sqrt(sum(x[k,(l+1):p]^2)) print(sum((A%*%x[k,]-b)^2)) } </code></pre> http://mathoverflow.net/questions/47025/least-square-given-constraint-on-subcomponents/47074#47074 Answer by S. Sra for Least square given constraint on subcomponents S. Sra 2010-11-23T09:11:17Z 2010-11-24T08:45:55Z <p>First eliminate$x_1$by solving an ordinary least squares, and then you need to <em>essentially</em> solve a problem of the form:$\min x_2^TMx_2$s.t.$\|x_2\|=g$, for appropriate$M$. This problem is the famous <em>trust-region subproblem</em>, aka, TRS. </p> <p>Please have a look at the following references (and references therein), which provide algorithms and discussion on how to solve such problems; perhaps you can simplify or adapt one of their methods:</p> <ol> <li>LSTRS: <a href="http://ta.twi.tudelft.nl/wagm/users/rojas/lstrs-paper.pdf" rel="nofollow">http://ta.twi.tudelft.nl/wagm/users/rojas/lstrs-paper.pdf</a></li> <li>Moré-Sorensen TRS algorithm (in the book on Trust-region subproblems)</li> <li><a href="http://www.optimization-online.org/DB_HTML/2002/09/530.html" rel="nofollow">http://www.optimization-online.org/DB_HTML/2002/09/530.html</a></li> </ol> <p>Depending on how large$A$is, or what kind of structure it has, different TRS methods may be preferred. Example, for small matrices, where you can afford to do Cholesky, the More-Sorensen method is usually very hard to beat. If your matrix is however large and sparse, then you might prefer the LSTRS method instead. </p> http://mathoverflow.net/questions/47025/least-square-given-constraint-on-subcomponents/47161#47161 Answer by FG for Least square given constraint on subcomponents FG 2010-11-23T23:16:33Z 2010-11-23T23:16:33Z <p>Writing$A = [A_1 A_2]$and taking without loss of generality$g=1$(scale$A_2$appropriately), your problem is equivalent to $$\min_{x_1,x_2}\ ||A_1 x_1 + A_2 x_2 - b||^2 \text{ s.t. } ||x_2||=1.$$ Notice that the solution of$\min_{x_1} ||A_1 x_1 - c||^2$can be obtained in closed form (assuming column independence in$A_1$): it is equal to$c^T P_1 c$with$P_1 = I - A_1 (A_1^T A_1)^{-1}A_1^T$(note$P_1$is positive semidefinite). Now you simply have to solve $$\min_{x_2}\ (b-A_2 x_2)^T P_1 (b-A_2 x_2) \text{ s.t. } ||x_2||=1$$ which can be done with standard techniques. I am not sure a closed-form solution can be obtained, but you can for example obtain a scalar equation in the Lagrange multiplier, which you solve numerically, and then obtain$x_2$. See also this <a href="http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint" rel="nofollow">link</a>, where the problem is reduced to a quadratic eigenvalue problem.</p> http://mathoverflow.net/questions/47025/least-square-given-constraint-on-subcomponents/47714#47714 Answer by kenny for Least square given constraint on subcomponents kenny 2010-11-29T19:50:39Z 2010-11-29T19:50:39Z <p>Hi all,</p> <p>I haven't understand all your answers. But I will look into them.</p> <p>Thank you so much for your replies.</p> <p>And just to clarify,$x_1$and$x_2\$ are vectors.</p>