TY - JOUR
T1 - A Hybrid Penalty Method for a Class of Optimization Problems with Multiple Rank Constraints
AU - LIU, TIANXIANG
AU - MARKOVSKY, IVAN
AU - PONG, TING KEI
AU - TAKEDA, AKIKO
N1 - Funding Information:
\ast Received by the editors June 24, 2019; accepted for publication (in revised form) by D. Orban June 25, 2020; published electronically September 1, 2020. https://doi.org/10.1137/19M1269919 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : The research of the first author is supported in part by JSPS KAKENHI grant 19H04069. The research of the second author has received funding from the European Research Council (ERC) under the European Union's Seventh Framework Programme (FP7/2007--2013)/ERC grant agreement 258581 ``Structured low-rank approximation: Theory, algorithms, and applications"" and Fond for Scientific Research Vlaanderen (FWO) projects G028015N ``Decoupling multivariate polynomials in nonlinear system identification"" and G090117N ``Block-oriented nonlinear identification using Volterra series""; and Fonds de la Recherche Scientifique (FNRS) --FWO Vlaanderen under Excellence of Science (EOS) Project 30468160 ``Structured low-rank matrix/tensor approximation: numerical optimization-based algorithms and applications."" The research of the third author is supported in part by Hong Kong Research Grants Council PolyU153004/18p. The research of the last author is supported in part by JSPS KAKENHI grants 17H01699 and 19H04069.
Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics.
PY - 2020/9
Y1 - 2020/9
N2 - In this paper, we consider the problem of minimizing a smooth objective over multiple rank constraints on Hankel structured matrices. These kinds of problems arise in system identification, system theory, and signal processing, where the rank constraints are typically "hard constraints.""To solve these problems, we propose a hybrid penalty method that combines a penalty method with a postprocessing scheme. Specifically, we solve the penalty subproblems until the penalty parameter reaches a given threshold, and then switch to a local alternating "pseudoprojection""method to further reduce constraint violation. Pseudoprojection is a generalization of the concept of projection. We show that a pseudoprojection onto a single low-rank Hankel structured matrix constraint can be computed efficiently by existing software such as SLRA [I. Markovsky and K. Usevich, J. Comput. Appl. Math., 256 (2014), pp. 278-292], under mild assumptions. We also demonstrate how the penalty subproblems in the hybrid penalty method can be solved by pseudoprojection-based optimization methods, and then present some convergence results for our hybrid penalty method. Finally, the efficiency of our method is illustrated by numerical examples.
AB - In this paper, we consider the problem of minimizing a smooth objective over multiple rank constraints on Hankel structured matrices. These kinds of problems arise in system identification, system theory, and signal processing, where the rank constraints are typically "hard constraints.""To solve these problems, we propose a hybrid penalty method that combines a penalty method with a postprocessing scheme. Specifically, we solve the penalty subproblems until the penalty parameter reaches a given threshold, and then switch to a local alternating "pseudoprojection""method to further reduce constraint violation. Pseudoprojection is a generalization of the concept of projection. We show that a pseudoprojection onto a single low-rank Hankel structured matrix constraint can be computed efficiently by existing software such as SLRA [I. Markovsky and K. Usevich, J. Comput. Appl. Math., 256 (2014), pp. 278-292], under mild assumptions. We also demonstrate how the penalty subproblems in the hybrid penalty method can be solved by pseudoprojection-based optimization methods, and then present some convergence results for our hybrid penalty method. Finally, the efficiency of our method is illustrated by numerical examples.
KW - Hankel structure
KW - Hybrid penalty method
KW - Pseudoprojection
KW - System identification
UR - http://www.scopus.com/inward/record.url?scp=85091992309&partnerID=8YFLogxK
U2 - 10.1137/19M1269919
DO - 10.1137/19M1269919
M3 - Journal article
AN - SCOPUS:85091992309
SN - 0895-4798
VL - 41
SP - 1260
EP - 1283
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
IS - 3
ER -