A branch and bound solver to find the largest minimum singular values among all submatrices.
B3MSV Bidirectional Branch and Bound(B3) subset selection using the the Minimum Singular Value (MSV) as the criterion.
Consider the following subset selection problem:
Given a tall (m x n, m>n) matrix, A, to find n rows of A such that the resulted n x n square submatrix has the largest MSV among all possible n x n submatrices.
This problem has many applications, where one wishes to square down a nonsquare matrix to get a wellposted problem (nonsingular, hence maximizing the MSV).
This problem has been studied in Linear Algebra for many decades. Many intuitive solutions have been proposed either analytically or numerically. But none of them, except two approaches, the exhaustive search and the branch and bound (BB) can guarantee the global optimality. Exhaustive search can only be used for very small m and n. Traditional BB is unidirectional, either upwards, where the subset is gragually expending until reaching the desired size, or downwards, where subset is shrinking one by one until the target size. The performance of both are very limited.
A novel B3 approach has been proposed for this problem (see reference below). In the B3, the search is carried out in both directions hence is much more efficient than unidirectional BB. Moreover, a novel determinant based pruning algorithm is implemented to replace timeconsuming singular value decomposition so that the overall efficincy is about several orders of magnitude faster than unidirectional approaches.
Initially, the submission included a pcode file and a help file only. Since the paper has been published now, the actual mfile is released for download from the FX.
The new version is developed for very large size problems:
n=1e5;m=20;
A = 1./randn(n,m);
tic, [B,s,op]=bbmsv(A); toc
It takes about 10 seconds with number of nodes evaluated less than 300.
Reference
Y. Cao and V. Kariwala, Bidirectional Branch and Bound for Controlled Variable Selection Part I: Principles and Minimum Singular Value Criterion, submitted to Computers and Chemical Engineering, 32(2008), 23062319
1.1  Updated to consider problems with a very large size matrix. 

recompile pfile to work with previous version (7.4 and before) 

update description 
Inspired: Bidirectional Branch and Bound Solvers for Worst Case Loss Minimization, Bidirectional Branch and Bound for Average Loss Minimization
Antonio (view profile)
Let A = [B; C] be a tall m by n block matrix, where B is a given p by n (p < n) full rank matrix, and C is a (mp) by n matrix from which rows are to be chosen such that the resulting n by n matrix, A_{prime} = [B; C_{prime}], has the smallest condition number. How must bbmsv be adapted to accommodate this situation? I'm not sure if the condition number has the monotonicity property... If not, I think the smallest minimum singular value will do.
Stefan Hoeser (view profile)
V. Poor (view profile)
Yi Cao (view profile)
Dear Ihsan
The code is not suppose to work with such large size. The problem mainly is from the line where a 122500 * 122500 matrix is going to be created, which requires about 120 GB memory.
For such large matrix, I guess it must be sparse, isn't it? If so, I may be able to find a solution for it although the computation time could be very long.
Hello, Nice job, working well efficiently. But there is a problem while working with very large size data. I gave input a data (matrix ) of size 122500 * 189. But there was an erro of memory, given below. Kindly help me to find such matlab function which can give singular values of a large size matrix.
>> b3msv(x);
??? Out of memory. Type HELP MEMORY for your options.
Error in ==> C:\Documents and Settings\ihsanulhaq\My Documents\My Completed
Downloads\Codes\b3msv\b3msv\b3msv.p>b3msv at 102
Thanks for pointing out this. This is due to comptibility of pcode in R2007b. From R2007b, the internal format of pfile has been changed, hence pfile compiled in R2007b cannot work with previous version. I have recompiled the pfile in R2007a. It should work with previous version now. Please let me know if you have any problem. It may take several hours for the update to be downloadable.
It doesn´t work.
.p file is corrupt