The Least Norm Solution of Under Determined Linear System

Question

Suppose I have a matrix

$$A= \begin{pmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 1& 0\\ \end{pmatrix} $$

where the variables are channel information like assume $X_1$, $X_2$, $X_3$ and $X_4$. Considering the typical least-squares problem

$$Y= AX+b$$

However, matrix $A$ is fat and, thus, $A^{T} A$ is not invertible. I cannot get $X_3$ or $X_4$ and they will be zero. I can use regularization and optimize joint least-squares and least-norm problem but that does not give me the same $X_1$ and $X_2$. Is there any way to solve this problem?

I tried to stack all the received vectors into matrix $Y$ and do the same for $A$ and $b$ to make matrix $A$ fat. However, due to the structure of $A$, it is still not invertible. Does anyone know how to solve this problem? Can I recover the solution for parameters based on what I get from regularized solution?

Answer 1

Least Squares solution is always well defined for Linear System of Equations.

In your case, which is under determined it means there are many solutions to the Linear Equations.
The Least Squares solution has nice property, it also minimizes the $ {L}_{2} $ norm of the solution (Least Norm Solution) hence it is well defined.

In practice, in order to solve this equation you need to use the pinv() function in MATLAB.
This function uses the Moore Penrose Pseudo Inverse Matrix of $ A $ to solve the equation:

x = pinv(A) * b

It basically decompose the Matrix using the Singular Value Decomposition (SVD) such that $ U S {V}^{T} = A $ and the rebuild the matrix $ {A}^{\dagger} = U {S}^{\dagger} {V}^{T} $ where $ {S}^{\dagger} $ is the result of inverting any non zero element of the diagonal matrix $ S $.

Update

The user @percusse said the following:

You just need A\b

You shouldn't use pinv for linear system solutions that's what I mean. Not only inefficient but also not accurate. There is no unique solution hence you can't talk about a least.

Backslash operator is optimized for all possible linear eq sets. Try it.

There is no least squares solutions for underdetermined systems because of the nontrivial nullspace. Anyways nevermind.

So, to make things clear.
The Least Squares solution always exists and it is also the Least Norm solution.
Namely, from the set $ \mathcal{B} = \left\{ x \mid \min_{x} \left\| A x - b \right\| \right\} $ there is one unique $ \hat{x} $ such that $ \hat{x} = \arg \min_{x} \left\| x \right\|_{2} \text{ subject to } \left\{ x \mid x \in \mathcal{B} \right\} $.

For instance:

for ii = 1:1e12
    numRows = 3;
    numCols = 27; %<! Must be bigger than 'numRows' for Under Determined System
    
    mA   = randn([numRows, numCols]);
    vB   = randn([numRows, 1]);
    vXLs = pinv(mA) * vB;
    vX   = mA \ vB;
    
    
    if(norm(vXLs) >= norm(vX))
        keyboard();
    end
    
    if(mod(ii, 1e4) == 0)
        disp(['Iteration Number - ', num2str(ii)]);
    end
    
end

Remarks:

• The difference arises for Under Determined System. For over / well determined system the solutions collide (Namely Tall Matrices which are the "Classic" case in LS problems).
• The Psuedo Inverse is much slower to use then the \ operator. If you're looking for any solution, use \. If you're looking for the Least Squares solution (The Least Squares solution is always the least norm solution) for Under Determined System you need to use the pinv() function.
• Proof and deeper analysis can be found in my Singular Value Decomposition (SVD) Presentation. Specifically this issue is on pages 50-60.
• Cleve Moler's (Inventor of MATLAB) post on Pseudo Inverse vs. \ - The World’s Simplest Impossible Problem.

Answer 2

Is there anyway to solve this problem

No, not really. Having such a matrix of reason-observation values being ill-formed simply is that you don't have more information. You cannot spawn information from nowhere.

Answer 3

As it can be observed, if $b=0$ , since $A$ is non square matrix. Thus inverse cannot exist.

Observe that the pseudo-inverse $A^TA$ does not exist, due to non independent columns.

The only way that the problem can be addressed is to introduce additional conditions on the signal such as sparsity. If $X$ has 2 or fewer non zero coefficients then there is a possible solution.

Answer 4

It means you will have a non-unique solution or redundancy. In your formulation, $X_4$ is completely free and $X_3$ is an offset parameter. You can deflate your matrix and obtain the full rank part to eliminate the unconstrained part.

In your example the solution is the family of

$$ \begin{bmatrix} X_1\\X_2 \end{bmatrix} = b - \begin{bmatrix} X_3\\X_3\end{bmatrix}$$

You have a degenerate case in which one of the variables is completely free but similar problems are pretty common in robotics with overactuated manipulators and so on for which you optimize within all the possible solutions.

Answer 5

The given matrix A is of rank 2, the third and the fourth columns are linear combinations of the first and second columns. So if the data matrix X is of rank lesser than or equal to the rank of A (i.e 2), you can recover the matrix X.

To know more about problems like this one, please read up on Orthogonal Matching Pursuit and Compressed sensing Matching Pursuit algorithms.

Answer 6

Since this question has an information-theoretic flavor, let us work over finite field $\mathbb F_2$. Rephrasing:

Given $$\mathrm A = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0\end{bmatrix}$$ and vector $\mathrm y \in \mathbb F_2^2$, find a vector $\mathrm x \in \mathbb F_2^4$ of minimal Hamming weight such that $\rm A x = y$.

---

Example

Suppose we are given

$$\mathrm y = \begin{bmatrix} 1\\ 1\end{bmatrix}$$

which is the 3rd column of $\rm A$ and also the sum of the 1st and 2nd columns. The solution set then has only two elements

$$\mathrm x \in \left\{ \begin{bmatrix} 0\\ 0\\ 1\\ 0\end{bmatrix}, \begin{bmatrix} 1\\ 1\\ 0\\ 0\end{bmatrix} \right\}$$

The former has Hamming weight $1$, while the latter has Hamming weight $2$.

---

Fortunately, matrix $\rm A$ is already in reduced row echelon form (RREF)

$$\rm A = \begin{bmatrix} \mathrm I_2 & \mathrm F\end{bmatrix}$$

and, thus, the solution set of the linear system $\rm A x = y$ is parameterized as follows

$$\mathrm x \in \left\{ \begin{bmatrix} \mathrm y\\ 0_2\end{bmatrix} + \begin{bmatrix} \mathrm F\\ \mathrm I_2\end{bmatrix} \mathrm z : \mathrm z \in \mathbb F_2^2 \right\}$$

Only $x_4$ depends on $z_2$. In order to avoid increasing the Hamming weight of $\mathrm x$ unnecessarily, let us choose $x_4 = z_2 = 0$. The solution set of the linear system $\rm A x = y$ is given by

$$\mathrm x \in \left\{ \begin{bmatrix} y_1\\ y_2\\ 0\\ 0\end{bmatrix} + z_1 \begin{bmatrix} 1\\ 1\\ 1\\ 0\end{bmatrix} : z_1 \in \mathbb F_2 \right\} = \left\{ \begin{bmatrix} y_1\\ y_2\\ 0\\ 0\end{bmatrix}, \begin{bmatrix} y_1+1\\ y_2+1\\ 1\\ 0\end{bmatrix} \right\} =: \mathcal X (\mathrm y)$$

Thus, the solution of minimal Hamming weight is

$$\mathrm x^* := \arg \min_{\mathrm x \in \mathcal X (\mathrm y)} w (\mathrm x)$$

where function $w : \mathbb F_2^4 \to \mathbb N$ returns the Hamming weight of its input. To summarize, we find the optimal solution by comparing the Hamming weights of two $4$-dimensional vectors. That is all!