# Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem:

$$||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0$$

where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is $m$-dimensional vector. Suppose that $m > n$

Suppose that we have SVD form of the matrix $Q$:

$$Q = U \Sigma V$$

where $U$ is $m \times m$ orthogonal matrix, $V$ is $n \times n$ orthogonal matrix and $\Sigma$ is $m \times n$ matrix constructed from $n \times n$ upper part, which is diagonal, and $(m - n) \times n$ down part, which consists of zeros:

$$\Sigma = \left( \begin{array} & \sigma_{1} & 0 & \ldots & 0 & 0 \\ 0 & \sigma_{2} & \ldots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & \sigma_{n - 1} & 0 \\ 0 & 0 & \ldots & 0 & \sigma_{n} \\ 0 & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 0 & 0 \\ \end{array} \right)$$

Then we can solve the problem that does not have inequality constraints:

$$||Q u - h^{0}||^{2} = ||U \Sigma V u - h^{0}||^{2} = ||\Sigma x - U^{T} h^{0}||^{2} = ||\Sigma x - x^{0}||^{2}$$

where $x = V u$ and $x^{0} = U^{T} h^{0}$. The we can easily find best vector $x$, and then compute corresponding $u$ from it.

Can we use this method for constrained problem?

Based on the algorithm description for Matlab's function lsqnonneg, and this paper on nonnegative least squares using an iterative algorithm, I don't think there's an easy way to solve nonnegative least squares problems using the SVD.

• Dear @littleO, thank you for your answer. I've read the articles you have mentioned. But it's still not clear for me why if we know SVD for of matrix a propri this cannot help us to solve LS problem (or simplify the problem). In the article you have mentioned it seems that they compute SVD form numerically, but in our case we pre-compute it analytically. – Ilya Palachev Mar 20 '14 at 16:03