Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums.
Robust methods like SVD or RRQR decompostion have complexity of order $O(n^3)$ for square matrices.
Can we do this in linear time or at least quadratic e.g. $O(n^2)$.