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



Efficient algorithm for solving a convex quadratic program
Using an [SVD](https://en.wikipedia.org/wiki/Singular-value_decomposition) $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$.


