Bidirectional Branch and Bound Minimum Singular Value Solver (V2)

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