# Soving overdetermined system of linear equations using SVD

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

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