A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
- PDF / 700,091 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 181 Views
A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery Shujun Bi1 · Shaohua Pan1 · Defeng Sun2 Received: 2 March 2017 / Accepted: 23 December 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract This paper concerns with a noisy structured low-rank matrix recovery problem which can be modeled as a structured rank minimization problem. We reformulate this problem as a mathematical program with a generalized complementarity constraint (MPGCC), and show that its penalty version, yielded by moving the generalized complementarity constraint to the objective, has the same global optimal solution set as the MPGCC does whenever the penalty parameter is over a certain threshold. Then, by solving the exact penalty problem in an alternating way, we obtain a multi-stage convex relaxation approach. We provide theoretical guarantees for our approach under a mild restricted eigenvalue condition, by quantifying the reduction of the error and approximate rank bounds of the first stage convex relaxation in the subsequent stages and establishing the geometric convergence of the error sequence in a statistical sense. Numerical experiments are conducted for some structured low-rank matrix recovery examples to confirm our theoretical findings. Our code can be achieved from https:// doi.org/10.5281/zenodo.3600639. Keywords Structured rank minimization · MPGCC · Exact penalty · Convex relaxation
The research of S. J. Bi and S. H. Pan is supported by the National Natural Science Foundation of China under project Nos. 11701186, 11971177 and 11571120; while the research of D. F. Sun is supported in part by Hong Kong Research Grant Council Grant PolyU153014/18p.
B
Shaohua Pan [email protected] Shujun Bi [email protected] Defeng Sun [email protected]
1
School of Mathematics, South China University of Technology, Guangzhou, China
2
Department of Applied Mathematics, The Hong Kong Polytechnic University, Kowloon, Hong Kong, China
123
S. Bi et al.
Mathematics Subject Classification 90C27 · 90C33 · 49M20
1 Introduction The task of noisy structured low-rank matrix recovery is to seek a low-rank matrix with a certain structure consistent with some noisy linear measurements. Let X be the target matrix to be recovered and b = AX + ξ be the noisy measurement vector, where A : Rn 1 ×n 2 → Rm is the sampling operator and ξ ∈ Rm is the noisy vector with ξ ≤ δ for some δ > 0. The noisy structured low-rank matrix recovery problem can be modeled as the rank minimization problem min
X ∈Rn 1 ×n 2
rank(X ) s.t. AX − b ≤ δ, X ∈ Ω ,
(1)
where Ω ⊆ Rn 1 ×n 2 is a compact convex set describing the structure of X . Throughout this paper, we assume that X is a global optimal solution of (1) with rank(X ) = r , and that the sampling operator A is defined by AX := (A1 , X , . . . , Am , X )T for X ∈ Rn 1 ×n 2 , where A1 , . . . , Am are the given matrices in Rn 1 ×n 2 . Such a structured rank minimization problem has wide applications in system
Data Loading...
