I have a problem that necessitates solving a large non-negative least-squares problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols) and nearly binary. However, A is not necessarily of full column-rank, causing my non-negative least-squares solver (http://www.jasoncantarella.com/webpage/index.php?title=Tsnnls) to fail. Is there an efficient algorithm that will allow me to select a maximum cardinality set of linearly-independent columns from A so that I can solve my least-squares problem?
By nearly binary do you mean most entries are $0$ or $1$ but a few are not? I will assume that all entries are $0,1.$ My main comments involve merely noting zero and non-zero.
To be sure of having maximum rank you will need to look at each column. You can start with any independent set (such as the set consisting of a single column) and then examine the rest of the columns in some order. If the next column is independent of the current set adjoin it as a new member otherwise discard it. This will result in a maximum size set (a basis of the column space). Depending on how sparse it is, it could be pretty easy to decide when the next column can be added, at least for a while.
Here are a few simple ideas to boost efficiency: