File Exchange

## Bidirectional Branch and Bound Minimum Singular Value Solver (V2)

version 1.1 (4.16 KB) by

A branch and bound solver to find the largest minimum singular values among all submatrices.

Updated

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 non-square matrix to get a well-posted problem (non-singular, 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 time-consuming singular value decomposition so that the overall efficincy is about several orders of magnitude faster than unidirectional approaches.

Initially, the submission included a p-code file and a help file only. Since the paper has been published now, the actual m-file 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), 2306-2319

Antonio

### 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 (m-p) 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

V. Poor

Yi Cao

### 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.

Ihsan ulhaq

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

Yi Cao

Thanks for pointing out this. This is due to comptibility of pcode in R2007b. From R2007b, the internal format of p-file has been changed, hence p-file compiled in R2007b cannot work with previous version. I have re-compiled the p-file 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.

David Cuesta

It doesn´t work.
.p file is corrupt