I have a problem that necessitates solving a large nonnegative leastsquares problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols) and nearly binary. However, A is not necessarily of full columnrank, causing my nonnegative leastsquares 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 linearlyindependent columns from A so that I can solve my leastsquares 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 nonzero. 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:


