Finite Rank Largest Subset Of Problems

In the thesis we discuss the Limit-Rank Maximum Subset(LRMS) problem: Given a matrix A 5Rm n , and an integer p r = rank(A) , how to select a columnsubmatrix A0 of A such that A0 which rank is p is the submatrix whichcolumn number is the biggest one of all the submatrices which rank is p .In general, the way to solve LRMS is the Enumeration method, which need more computational time. In Chapter 3, we take a divide-and-conquer method to deal with LRMS problem. We give the sufficient and necessary condition of the problem, and prove that when the matrix A is column-divided, we can use the divide-and-conquer method to solve the LRMS problem. Furthermore, we show when a matrix is column-divided and how to divide a matrix which is column-divided based on the classic QR factorization. Numerical examples are also given to show that the divide-and-conquer method is efficient.In Chapter 4, we discuss the matrix which is non-column-divided. According to the idea of column privoting QR method, we bring forward the greedy methods. If /is the column index subset which we have known, then we choose a column index i* from the residual subset I0 \ I , such thatwhich k is the rank of A(:,I). This method is called the Forward-choice Greedy Algorithm. We also have the Backward-choice Greedy Algorithm: If J is the column index subset which we have known, then we choose a column index j' from the subset J , such thatwhich k is the rank of A(:, J) . Combined with the two greedy algorithms, we alsogive a Combinative-choice Greedy Algorithm. There are some numerical examples to show that the greedy algorithms work well.Finally, we consider the numerical rank LRMS. The methods above can also be used to deal with the numerical rank LRMS.