Suppose I have a system:


$$
Ax = b
$$


where $A$ is a $m$ by $n$ matrix which is less than full rank (neither full column nor row rank). In my particular case $m<n$.


I'd like a combination of a minimum norm solution (for elements of $x$ which are not determined and a least squares solution for those that are determined or over determined).


I know I can approximate this with Tikhonov regularization:


$$
\mathop{\text{minimize}}\limits\_x \|Ax-b\|^2 + \alpha\|x\|^2.
$$


But this is not ideal as the regularizer tugs on all elements of $x$ not just those left undetermined. If I make $\alpha$ too large then my $x$ at determined or over determined elements will not be optimal (w.r.t. $\|Ax-b\|^2$). If $\alpha$ is too small, I imagine I run into conditioning issues.


Is there no way to formulate this correctly using some sort null space/QR decomposition?


**Update:**
See accepted answer, but for completeness here's a full recipe:
\begin{align}
Ax &= b\\
AE &= QR &\text{rank-revealing QR decomposition of A}\\
AE &= Q\left(\begin{array}{c}I\\0\end{array}\right)\left(\begin{array}{cc}R\_1&R\_2\end{array}\right) & \text{only keep $r$ (rank) many rows of $R$}\\
\left(\begin{array}{c}R\_1^T\\R\_2^T\end{array}\right)F &= VT\_\text{full} &\text{rank-revealing QR decomposition of $\left(\begin{array}{c}R\_1^T\\R\_2^T\end{array}\right)$} \\
\left(\begin{array}{c}R\_1^T\\R\_2^T\end{array}\right)F &= V\left(\begin{array}{c}I\\0\end{array}\right)T & \text{only keep $r$ many rows of $T$}\\
AE &= Q\left(\begin{array}{c}I\\0\end{array}\right)FT^T\left(\begin{array}{cc}I&0\end{array}\right)V^T
\\
x &= A^+b\\
x &= EV\left(\begin{array}{c}I\\0\end{array}\right)T^{-T}F^T\left(\begin{array}{cc}I&0\end{array}\right)Q^Tb
\end{align}



General method for under and over determined systems?
The [Moore-Penrose pseudoinverse](http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse) is probably what you're looking for. The *pseudoinverse solution* $A^+b$ is the smallest norm $x$ such that $\|Ax-b\|\_2$ is minimized. It can be computed using QR decomposition although you have to use rank-revealing QR when $A$ does not have full column rank. A more complete explanation is given [here](http://www.irisa.fr/sage/wg-statlin/WORKSHOPS/LEMASSOL05/SLIDES/QR/Guyomarch.pdf).


