Code covered by the BSD License

Highlights from Bidirectional Branch and Bound Minimum Singular Value Solver (V2)

4.0
4.0 | 4 ratings Rate this file 6 Downloads (last 30 days) File Size: 4.16 KB File ID: #17480 Version: 1.1

Bidirectional Branch and Bound Minimum Singular Value Solver (V2)

by

Yi Cao (view profile)

11 Nov 2007 (Updated )

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

File Information
Description

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

Acknowledgements
MATLAB release MATLAB 7.4 (R2007a)
17 Nov 2009 Stefan Hoeser

Stefan Hoeser (view profile)

05 Apr 2009 V. Poor

V. Poor (view profile)

09 Jan 2009 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.

Comment only
03 Jun 2008 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

15 Jan 2008 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.

Comment only
12 Jan 2008 David Cuesta

It doesnÂ´t work.
.p file is corrupt

12 Nov 2007

update description

15 Jan 2008

recompile p-file to work with previous version (7.4 and before)

09 Jan 2009 1.1

Updated to consider problems with a very large size matrix.