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

982 Views Asked by At

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?

1

There are 1 best solutions below

1
On

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.