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

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

作　　者：张振跃[1] 叶环球[1] 

机构地区：[1]浙江大学玉泉校区数学系,杭州310027

出　　处：《计算数学》2002年第2期229-242,共14页Mathematica Numerica Sinica

基　　金：国家重点基础研究专项经费(G19990328);教育部高校骨干教师基金资助.

摘　　要：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.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.

关 键 词：秩约束 子集选择问题 分而治之解法 信息检索 列可分矩阵 整数规划 计算机信息处理 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]