Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?

Question

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be-as in - Is the improvement in speed by many factors!?

1) Minimizing a convex function L(X) in one matrix variable with orthogonality constraints over the matrix-essentially in my case this ends up to solving an eigen-decomposition.

2) Minimizing the same convex function L(X) with a single linear constraint in X.

I know that 2) should be faster. But what is the direction of work I need to do- to compare the improvement in speed-especially in terms of using the fastest available eigen solver for 1)-what would be the corresponding fastest approach to solve 2)?

Details: Example Formulation 1) Minimize $Tr(X^TAX)$ over $X$ under a constraint that $X^TX=I$

Example Formulation 2) Minimize $Tr(X^TAX)$ over $X$ under a single linear constraint, $Tr~X^TC=b$ over $X$ where $A$ is a known p.s.d matrix , $b$ is a constant (scalar) $\in \mathbb{R^+}$ and $C$ is a constant matrix with real-entries. Hence making $Tr(X^TAX)$ convex.

The dimension of $X$ in this problem setting varies from 5000 by 2 and up until 50000 by 3. So, the number of columns are not many. $A$ is a sparse matrix, with the amount of sparsity dependent on a tuning parameter of a kernel function that generates the matrix $A$. On a holistic sense the sparsity does range a lot from very sparse to not too sparse and is data and problem dependent.

Which would be the fastest to solve and by what factor!? And what are the example -fastest possible methods you would use for each individual problem-while coming to this conclusion. Would you come to this conclusion from a theoretical aspect- in terms of how the problem were formulated? If so, please go over that too.

Answer 1

For a symmetric and positive definite matrix $A$, the problem $\min Tr~X^TAX$ subject to $Tr~X^TC=b [\in R_+]$ can be solved by introducing a Lagrange multipliers and setting the gradient of the Lagrangian to zero. The result is $X=\lambda Z$, where $Z=A^{-1}C$. Inserting this into the constraints gives the multiplier $\lambda=b/Tr~C^TA^{-1}C$. As $C$ has only a few columns, the dominant work is therefore that for computing $Z$, which means a solve for a fixed positive definite matrix with a few right hand sides. (If there were $s$ linear constraints, one would end up with an $s\times s$ system for the multiplier vector.)
If the sparsity of $A$ is such that upon reordering you can compute a Cholesky factor $R$, so that $A=R^TR$ then solving $R^TY=C$ and $RZ=Y$ gives the solution $X=\lambda Z$, where $\lambda=b/||Y||^2$ (in the Frobenius norm). If a factorization is too expensive, you need to employ conjugate gradients.

For a symmetric and positive definite matrix $G$, the problem $\min Tr~X^TGX$ subject to $X^TX=1$ is solved (for an $m\times n$ matrix $X$) by taking as columns of $X$ orthogonal eigenvectors corresponding to the $n$ smallest eigenvalues of $G$. This is more expensive to compute when $A$ can be factored, but if a factorization is not feasible, the Lanczos iteration will have complexity comparable to that for the other problem, and this will become better the more columns $X$ has.

Answer 2

Minimizing $Tr(X^TAX)$ subject to a linear constraint on $X$ is clearly a simpler problem than minimizing it subject to a quadratic constraint. You can do the former in a single step -- the solution is simply the solution of a single, linear, saddle point problem.