1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ilya Palachev Mar 20 '14 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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