2
$\begingroup$

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$$

$\endgroup$
  • 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$ – user35593 Apr 16 '18 at 17:11
  • $\begingroup$ @user35593 Could you elaborate more on finding the base of the orthogonal complement? $\endgroup$ – O. Richard Apr 16 '18 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$ – user35593 Apr 16 '18 at 17:52
  • 1
    $\begingroup$ See my answer here mathoverflow.net/a/244126/39129 $\endgroup$ – Cristóbal Guzmán Apr 16 '18 at 18:18
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your answer! What is the complexity of computing SVD in this case? $\endgroup$ – O. Richard Apr 16 '18 at 16:33
  • $\begingroup$ Is such complexity optimal in any sense? $\endgroup$ – O. Richard Apr 16 '18 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$ – Federico Poloni Apr 16 '18 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$ – Rodrigo de Azevedo Apr 17 '18 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$ – Federico Poloni Apr 17 '18 at 14:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.