秩约束子集选择问题的分而治之解法

A DIVIDE-AND-CONQUER ALGORITHM FOR THE RANK-CONSTRAINED SUBSET SELECTION PROBLEM

We consider the rank-constrained subset selection problem (RCSS): Given a matrix A and an integer p ≤ rank(A), find the largest submatrix A0 consisting of some columns of A with rank(A0) = p. The RCSS problem is generally NP- hard. This paper focuses on a divide-and-conquer (DC) algorithm for solving the RCSS problem: partition the matrix A into several small column blocks: A = [Al,……) Ak] with a certain column permutation II and decompose p to p1 + p2 + ……+ pk such that solutions of the RCSS problems for smaller couples form a solution of the original RCSS problem. We show that the optimal solution of the RCSS problem can be found by DC algorithm for each p ≤ rank(A), if and only if A is column-partitionable, i. e., rank(A) = Σ rank(Ai). Based upon QR decomposition, a fast algorithm for determining the column partition is offered. Our divide-and-conquer algorithm is also quite efficient even A is approkimately column-partitionable.