Given a dense matrix $$A \in R^{m \times n}, m >> n; max(m) \approx 100000 $$ what is the best way to find its null-space basis within some tolerance $\epsilon$? Based on that basis can I then say that certain cols are linearly dependent within $\epsilon$? In other words, having null space basis computed, what columns of $A$ have to be removed in order to get nonsingular matrix?References are appreciated.
Null-space of a rectangular dense matrix
linear algebra
Standard methods for determining the null space of a matrix are to use a QR decomposition or an SVD. If accuracy is paramount, the SVD is preferred; the QR decomposition is faster.Using the SVD, if $A = U\Sigma V^{H}$, then columns of $V$ corresponding to small singular values (i.e., small diagonal entries of $\Sigma$) make up the a basis for the null space. The relevant tolerance here is what one considers a small singular value. MATLAB, for instance, takes small to be $\max(m,n) \cdot \varepsilon$, where $\varepsilon$ is related to machine accuracy (see here in MATLAB's documentation).Using the QR decomposition, if $A^{T} = QR$, and the rank of $A$ is $r$, then the last $n-r$ columns of $Q$ make up the nullspace of $A$, assuming that the QR decomposition is rank revealing. To determine $r$, calculate the number of entries on the main diagonal of $R$ whose magnitude exceeds a tolerance (similar to that used in the SVD approach).Don't use LU decomposition. In exact arithmetic, it is a viable approach, but with floating point arithmetic, the accumulation of numerical errors makes it inaccurate.Wikipedia covers these topics here.