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 gene...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.展开更多
Skorokhod's representation theorem states that if on a Polish space,there is a weakly convergent sequence of probability measures μnw→μ0,as n →∞,then there exist a probability space(Ω,F,P) and a sequence of ...Skorokhod's representation theorem states that if on a Polish space,there is a weakly convergent sequence of probability measures μnw→μ0,as n →∞,then there exist a probability space(Ω,F,P) and a sequence of random elements Xnsuch that Xn→ X almost surely and Xnhas the distribution function μn,n = 0,1,2,... We shall extend the Skorokhod representation theorem to the case where if there are a sequence of separable metric spaces Sn,a sequence of probability measures μnand a sequence of measurable mappings n such that μnn-1w→μ0,then there exist a probability space(Ω,F,P) and Sn-valued random elements Xndefined on Ω,with distribution μnand such that n(Xn) → X0 almost surely. In addition,we present several applications of our result including some results in random matrix theory,while the original Skorokhod representation theorem is not applicable.展开更多
文摘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.
基金supported by the Fundamental Research Funds for the Central UniversitiesProgram for Changjiang Scholars and Innovative Research Team in UniversityNational Natural Science Foundation of China(Grant Nos.11301063 and 11171057)
文摘Skorokhod's representation theorem states that if on a Polish space,there is a weakly convergent sequence of probability measures μnw→μ0,as n →∞,then there exist a probability space(Ω,F,P) and a sequence of random elements Xnsuch that Xn→ X almost surely and Xnhas the distribution function μn,n = 0,1,2,... We shall extend the Skorokhod representation theorem to the case where if there are a sequence of separable metric spaces Sn,a sequence of probability measures μnand a sequence of measurable mappings n such that μnn-1w→μ0,then there exist a probability space(Ω,F,P) and Sn-valued random elements Xndefined on Ω,with distribution μnand such that n(Xn) → X0 almost surely. In addition,we present several applications of our result including some results in random matrix theory,while the original Skorokhod representation theorem is not applicable.
