Underdetermined Linear System

In high-dimensional Machine Learning, we often need to solve underdetermined linear systems $y=Xw$, where the feature number is much higher than the sample number ($d\gg n$). For overdetermined linear systems, use Linear Regression. We can also think of these systems as for the Linear Regression problem. Except here, there are infinite solutions that can achieve zero MSE. So instead of aiming at least square error, we aim for the least norm for underdetermined linear systems.

L2 Norm

We can easily show that $w_{\ln }=X^T(X{X}^T{)}^{-1}y$ is a solution to the system (we always assume that $X$ has full row rank). We can also use KKT to get the solution.

• Don’t mix it up with the MSE solution $w_{\mathrm{LS}}=(X^{T}X{)}^{-1}{X}^{T}y$.

We claim that $w_{\ln }$ has the least L2 norm: for any solution $w$, we have

$$\begin{array}{rl}\Vert w{\Vert }_2^2& =\Vert w-w_{\ln }+w_{\ln }{\Vert }_2^2\\ & =\Vert w-w_{\ln }{\Vert }_2^2+\Vert w_{\ln }{\Vert }_2^2+2(w-w_{\ln }{)}^T{w}_{\ln }\\ & =\Vert w-w_{\ln }{\Vert }_2^2+\Vert w_{\ln }{\Vert }_2^2+2(X(w-w_{\ln }){)}^T(X{X}^T{)}^{-1}y\\ & =\Vert w-w_{\ln }{\Vert }_2^2+\Vert w_{\ln }{\Vert }_2^2+0\\ & \ge \Vert w_{\ln }{\Vert }_2^2.\end{array}$$

We can also solve the Optimization problem ${\mathrm{argmin}}_w\Vert w{\Vert }_2^2\text{ subject to }Xw=y$ to get $w_{\ln }$.

• The geometric perception of the solution is $w_{\ln }={\mathrm{proj}}_{\{w:Xw=y\}}0$. Therefore, $w_{\ln }$ achieves optimality.

L1 Norm

We can think of the least ${\ell }_2$ norm solution as applying L2 Regularization to Mean Squared Error (which is equivalent to Ridge Regression) on underdetermined linear systems. When using an L1 Regularization to general linear systems, we get LASSO.

L1 Regularization/sparsity/feature selection is especially important for underdetermined linear systems.