Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?
$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ If b is not orthogonal to the kernel of the transpose of A the quadratic expression can get arbitrarily small. On the other hand if b is orthogonal to the kernel you can choose a base of the orthogonal complement and solve the corresponding linear equation. $\endgroup$– user35593Commented Apr 16, 2018 at 17:11
-
$\begingroup$ @user35593 Could you elaborate more on finding the base of the orthogonal complement? $\endgroup$– O. RichardCommented Apr 16, 2018 at 17:49
-
$\begingroup$ thats actually the image of A. If A has full rank you can set x=Ay and minimize over y $\endgroup$– user35593Commented Apr 16, 2018 at 17:52
-
1$\begingroup$ See my answer here mathoverflow.net/a/244126/39129 $\endgroup$– Cristóbal GuzmánCommented Apr 16, 2018 at 18:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + \frac12 \sigma_i^2 y_i^2,$$ which should be trivial because the variables are separated. The whole algorithm costs $O(nm^2)$, assuming you are careful in representing $U$ as a product of rotations (which is not completely trivial to do in Matlab/Python/whatever you are using: in Matlab, you'd have to start with a QR factorization of $A$ [c,R] = qr(A,b), for instance, and then do an SVD of $R$; in Python, I am afraid you need numpy.linalg.qr with option raw). Or you can get $O(n^2m)$ if you just ignore the issue and use library SVD which returns a full matrix $U$.
answered Apr 16, 2018 at 16:30
-
$\begingroup$ Thank you very much for your answer! What is the complexity of computing SVD in this case? $\endgroup$ Commented Apr 16, 2018 at 16:33
-
$\begingroup$ Is such complexity optimal in any sense? $\endgroup$ Commented Apr 16, 2018 at 17:01
-
$\begingroup$ @O.Richard No, it's not optimal, but almost, in practice. It can't be less than $O(mn)$ anyway, because that's the time you need to read the matrix $A$. I think that using for the SVD the various nontrivial (and very impractical) algorithms for fast matrix multiplication you can lower it to $O(nm^{1.37})$, and it's an open problem whether it can go down to $O(nm^{1+\varepsilon})$. But on a real-world problem, I doubt they will give any improvement. $\endgroup$ Commented Apr 16, 2018 at 17:06
-
$\begingroup$ Since you square $S$, I assume you're using the economy SVD. However, shouldn't the quadratic terms be summed till $i=m$ only? After all, $A$ is tall. $\endgroup$ Commented Apr 17, 2018 at 13:27
-
1$\begingroup$ @RodrigodeAzevedo Good point --- the $\sigma_i$ are defined up to $m$ only; the rest can be taken to be zeros. The $c_i$ go up to $n$, though, and in particular there is no minimum if $c_i \neq 0$ for some $i>m$ (or whenever $\sigma_i=0$). This is more or less equivalent to what user35593 said in a comment above: $b$ must be in the range of $A$ for the minimum to exist finite. $\endgroup$ Commented Apr 17, 2018 at 14:30