I have been trying to solve a system of linear equations $$\mathbf{Ax}=\mathbf{b}$$ Where $\mathbf{A}$ is a $m\times n$ matrix, (such that $m>n$) and $\mathbf{x}=\{x_1 ,x_2, x_3...x_n\}$ and $\mathbf{b}=\{b_1 ,b_2, b_3...b_n\}$ are vectors of length $n$. In particular, I aim to minimize the norm $||\mathbf{Ax-b}||$.

I am doing this by performing the singular value decomposition of matrix $\mathbf{A}$ as $\mathbf{U w^{-1}} V^{T}$. Components of the vector $\mathbf{x}$ corresponding to the minimum norm are then given simply by $\mathbf{x=VwU^{T}b}$.

This method gives me a set of $x_i$ for minimum possible value of $||\mathbf{Ax-b}||$.

My question is as follows, is there any method to seek the minimum of $||\mathbf{Ax-b}||$ while forcing one of the components of $\mathbf{x}$, say $x_n$ to have non negative values?


For the first part either you wrote $A$ by accident or something but if

$$ A = U \Sigma V^{T} \tag{1} $$

and we have

$$ Ax=b \\ U \Sigma V^{T} x = b \\ x = V\Sigma^{\dagger}U^{T}b \tag{2} $$

for the second part, you need to use linear programming to enforce that $x_{n}$ be non-negative. I.e

$$ \textrm{ minimize } c^{T}x \\ \textrm{ subject to } Ax \leq b \\ \textrm{ and } x \geq 0 \tag{3}$$

Typically we have

$$ lb \leq x \leq ub \tag{4} $$

Which is modified afterward

  • $\begingroup$ Thanks, let me try that $\endgroup$ – Abhijit Oct 5 '18 at 6:43

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.