pith. sign in

arxiv: 1906.10396 · v1 · pith:3V62W2P3new · submitted 2019-06-25 · 🧮 math.OC

A hybrid penalty method for a class of optimization problems with multiple rank constraints

Tianxiang Liu , Ivan Markovsky , Ting Kei Pong , Akiko Takeda This is my paper

Pith reviewed 2026-05-25 16:42 UTC · model grok-4.3

classification 🧮 math.OC
keywords optimizationrank constraintsHankel structurepenalty methodspseudo-projectionsystem identificationconvergence
0
0 comments X

The pith

A hybrid penalty method with pseudo-projection post-processing solves optimization under multiple rank constraints on Hankel matrices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper considers the minimization of a smooth objective function subject to multiple rank constraints on Hankel-structured matrices, a setting common in system identification and signal processing. It proposes a hybrid penalty method that first solves a sequence of penalized problems and then applies a post-processing step using alternating pseudo-projections to further enforce the constraints. This hybrid strategy is designed to balance objective minimization with feasibility for the hard rank constraints. The approach relies on the ability to compute pseudo-projections for individual constraints efficiently and includes analysis of how to solve the penalized subproblems along with convergence properties.

Core claim

The central claim is that a hybrid penalty method, which combines a penalty method with a post-processing scheme using local alternating pseudo-projections, can be used to solve problems of minimizing a smooth objective over multiple rank constraints on Hankel-structured matrices. The method proceeds by solving the penalty subproblems until the penalty parameter reaches a given threshold and then switches to the pseudo-projection method to reduce constraint violation. Under mild assumptions, pseudo-projections onto single low-rank Hankel-structured matrix constraints can be computed efficiently, the penalty subproblems can be solved by pseudo-projection-based optimization methods, and the hy

What carries the argument

The hybrid penalty method that switches from penalty minimization to alternating pseudo-projections once the penalty parameter is below a threshold.

If this is right

  • The penalty subproblems can be solved using pseudo-projection-based optimization methods.
  • Some convergence results hold for the hybrid penalty method.
  • The method can be illustrated on numerical examples from relevant applications.
  • The pseudo-projection step further reduces constraint violation after the penalty phase.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method may offer advantages in applications like system identification by producing solutions that better satisfy the rank conditions.
  • Similar hybrid approaches could be explored for optimization problems with other types of structured constraints.
  • Further analysis might examine the practical performance on problems with more than a few constraints.

Load-bearing premise

That a pseudo-projection onto a single low-rank Hankel-structured matrix constraint can be computed efficiently under mild assumptions.

What would settle it

A test case in which applying the alternating pseudo-projection post-processing fails to decrease the violation of the rank constraints compared to continuing with the penalty method alone.

Figures

Figures reproduced from arXiv: 1906.10396 by Akiko Takeda, Ivan Markovsky, Tianxiang Liu, Ting Kei Pong.

Figure 1
Figure 1. Figure 1: Comparing terminating function values among [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparing constraint violations and CPU times (in seconds) among [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
read the original abstract

In this paper, we consider the problem of minimizing a smooth objective over multiple rank constraints on Hankel-structured matrices. This kind of problems arises 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 post-processing scheme. Specifically, we solve the penalty subproblems until the penalty parameter reaches a given threshold, and then switch to a local alternating "pseudo-projection'' method to further reduce constraint violation. Pseudo-projection is a generalization of the concept of projection. We show that a pseudo-projection onto a {\em single} low-rank Hankel-structured matrix constraint can be computed efficiently by existing softwares such as SLRA (Markovsky and Usevich, 2014), under mild assumptions. We also demonstrate how the penalty subproblems in the hybrid penalty method can be solved by pseudo-projection-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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript addresses minimization of a smooth objective subject to multiple rank constraints on Hankel-structured matrices, a setting arising in system identification and signal processing. It proposes a hybrid penalty method that solves penalized subproblems until a penalty-parameter threshold is reached and then switches to a local alternating pseudo-projection scheme to reduce constraint violation. The paper asserts that a pseudo-projection onto a single low-rank Hankel constraint can be obtained efficiently via the SLRA package under mild assumptions, shows how penalty subproblems can be solved by pseudo-projection-based methods, states some convergence results for the overall hybrid scheme, and illustrates performance on numerical examples.

Significance. If the convergence guarantees hold and the single-constraint primitive extends reliably to the multiple-constraint case, the hybrid approach would supply a practical, software-leveraging algorithm for a class of structured low-rank problems. The explicit use of an existing, mature package (SLRA) for the core primitive is a concrete computational advantage.

major comments (2)
  1. [Abstract] Abstract: the convergence results for the hybrid method are presented after invoking the SLRA-based pseudo-projection primitive, yet the manuscript supplies no explicit statement or verification of the 'mild assumptions' under which the single-constraint computation is valid once several independent rank-Hankel constraints are active simultaneously; this assumption set is load-bearing for the claimed guarantees.
  2. The description of the post-processing phase (local alternating pseudo-projection) does not contain an argument that coordinate-wise application of the single-constraint primitive preserves feasibility or inherits the convergence properties when the constraints are independent; without this, the extension from the single-constraint case to the target multi-constraint problem remains unestablished.
minor comments (2)
  1. The term 'pseudo-projection' is introduced as a generalization of projection but its precise definition and relation to the standard projection operator are not restated in the algorithmic sections, which may hinder readability.
  2. The numerical examples would benefit from a table reporting both final constraint violation and objective value for the hybrid method versus a pure penalty baseline.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the convergence results for the hybrid method are presented after invoking the SLRA-based pseudo-projection primitive, yet the manuscript supplies no explicit statement or verification of the 'mild assumptions' under which the single-constraint computation is valid once several independent rank-Hankel constraints are active simultaneously; this assumption set is load-bearing for the claimed guarantees.

    Authors: We agree that an explicit statement would strengthen the presentation. The mild assumptions concern properties of a single Hankel matrix (structure, rank, and the conditions under which SLRA computes the pseudo-projection). Because the multiple constraints act on distinct, independent matrices, these assumptions apply separately to each constraint with no interaction. In the revision we will add a clarifying sentence to the abstract (and introduction) stating that the assumptions hold independently for each constraint, thereby supporting the claimed guarantees for the multi-constraint hybrid scheme. revision: yes

  2. Referee: The description of the post-processing phase (local alternating pseudo-projection) does not contain an argument that coordinate-wise application of the single-constraint primitive preserves feasibility or inherits the convergence properties when the constraints are independent; without this, the extension from the single-constraint case to the target multi-constraint problem remains unestablished.

    Authors: The constraints operate on separate matrices and are therefore independent. Consequently, each pseudo-projection step enforces its own constraint without affecting the others, so alternating application reaches joint feasibility. The single-constraint convergence analysis then extends by iteration. We acknowledge that the current text leaves this reasoning implicit. In the revision we will insert a short paragraph in the post-processing section that makes the independence argument explicit and notes the direct inheritance of the single-case properties. revision: yes

Circularity Check

1 steps flagged

Minor self-citation to SLRA for single-constraint pseudo-projection; hybrid method and convergence results remain independent

specific steps
  1. self citation load bearing [Abstract]
    "We show that a pseudo-projection onto a single low-rank Hankel-structured matrix constraint can be computed efficiently by existing softwares such as SLRA (Markovsky and Usevich, 2014), under mild assumptions."

    The key algorithmic primitive (pseudo-projection) is justified solely by citation to prior work whose author list overlaps with the current paper; the hybrid method's subproblem solver and convergence claims depend on this primitive being available, though the paper does not derive or verify the SLRA step itself.

full rationale

The paper proposes a hybrid penalty method for optimization with multiple rank-Hankel constraints, combining standard penalty subproblems with a post-processing alternating pseudo-projection scheme. It invokes the external SLRA software (cited to Markovsky and Usevich 2014) only for the single-constraint pseudo-projection primitive under mild assumptions, then states convergence results for the overall hybrid scheme. No equations reduce any claimed convergence, efficiency, or feasibility guarantee to a quantity fitted or defined from the present paper's own data or parameters. The self-citation is present but not load-bearing for the central derivation chain, which rests on standard penalty frameworks plus the cited external primitive.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claim rests on the external SLRA solver for single-constraint pseudo-projections and on standard convergence theory for penalty methods; the hybrid switching rule and the definition of pseudo-projection are the main additions.

free parameters (1)
  • penalty threshold
    The value at which the algorithm switches from penalty subproblems to the local pseudo-projection post-processing step.
axioms (1)
  • domain assumption Mild assumptions allow efficient computation of pseudo-projection onto a single low-rank Hankel constraint via SLRA
    Invoked to justify calling existing software for the single-constraint case inside the hybrid method.
invented entities (1)
  • pseudo-projection no independent evidence
    purpose: Generalized projection operator used in the local alternating post-processing step
    New concept introduced to handle the structured rank constraint after the penalty phase

pith-pipeline@v0.9.0 · 5723 in / 1394 out tokens · 38892 ms · 2026-05-25T16:42:18.981093+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    M. Chu, N. Del Buono, L. Lopez and T. Politi , On the low-rank approximation of data on the unit sphere , SIAM J. Matrix Anal. Appl., 27 (2005), pp. 46–60

    work page 2005

  2. [2]

    Eckart and G

    C. Eckart and G. Young , The approximation of one matrix by another of lower rank , Psychometrika, 1 (1936), pp. 211–218

    work page 1936

  3. [3]

    F azel, Matrix Rank Minimization with Applications , PhD thesis, Elec

    M. F azel, Matrix Rank Minimization with Applications , PhD thesis, Elec. Eng. Dept., Stanford University, 2002

    work page 2002

  4. [4]

    Golub and C

    G. Golub and C. V an Loan , Matrix Computations, Johns Hopkins University Press, 1996

    work page 1996

  5. [5]

    Ishteva, K

    M. Ishteva, K. Usevich and I. Markovsky , Factorization approach to structured low-rank approximation with applications, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1180–1204

    work page 2014

  6. [6]

    N. K. Karmarkar and Y. N. Lakshman , On approximate GCDs of univariate polynomials , J. Symbolic Comput., 26 (1998), pp. 653–666

    work page 1998

  7. [7]

    A. S. Lewis, D. R. Luke and J. Malick , Local linear convergence for alternating and averaged nonconvex projections, Found. Comput. Math., 9 (2007), pp. 485–513

    work page 2007

  8. [8]

    T. Liu, T. K. Pong and A. Takeda , A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems , To appear in Math. Program., DOI:10.1007/s10107-018-1327-8

    work page doi:10.1007/s10107-018-1327-8

  9. [9]

    D. R. Luke , Prox-regularity of rank constraint sets and implications for algorithms , J. Math. Imaging Vision, 47 (2013), pp. 231–238

    work page 2013

  10. [10]

    Markovsky, Structured low-rank approximation and its applications , Automatica J

    I. Markovsky, Structured low-rank approximation and its applications , Automatica J. IFAC, 44 (2008), pp. 891–909

    work page 2008

  11. [11]

    Markovsky, Recent progress on variable projection methods for structured low-rank approxi- mation, Signal Processing, 96 (2014), pp

    I. Markovsky, Recent progress on variable projection methods for structured low-rank approxi- mation, Signal Processing, 96 (2014), pp. 406–419

    work page 2014

  12. [12]

    Markovsky, Low-Rank Approximation: Algorithms, Implementation, Applications , Springer, 2019

    I. Markovsky, Low-Rank Approximation: Algorithms, Implementation, Applications , Springer, 2019

    work page 2019

  13. [13]

    Markovsky, A

    I. Markovsky, A. F azzi and N. Guglielmi , Applications of Polynomial Common Factor Computation in Signal Processing , In Latent Variable Analysis and Signal Separation, Lecture Notes in Computer Science, Springer, 2018, pp. 99–106

    work page 2018

  14. [14]

    Markovsky, T

    I. Markovsky, T. Liu, and A. Takeda , Subspace Methods for Common Dynamics Estimation , Technical report, Dept. ELEC, Vrije Universiteit Brussel, 2019

    work page 2019

  15. [15]

    Markovsky and K

    I. Markovsky and K. Usevich , Software for weighted structured low-rank approximation , J. Comput. Appl. Math., 256 (2014), pp. 278–292

    work page 2014

  16. [16]

    Markovsky and K

    I. Markovsky and K. Usevich , Structured low-rank approximation with missing data , SIAM J. Matrix Anal. Appl., 34 (2013), pp. 814–830

    work page 2013

  17. [17]

    Markovsky and S

    I. Markovsky and S. V an Huffel , Overview of total least-squares methods , Signal Processing, 87 (2007), pp. 2283–2302

    work page 2007

  18. [18]

    J. -M. Papy, L. De Lathauwer and S. V an Huffel , Common pole estimation in multi-channel exponential data modeling, Signal Processing, 86 (2006), pp. 846–858

    work page 2006

  19. [19]

    R. A. Poliquin and R. T. Rockafellar , A calculus of prox-regularity, J. Convex Anal., 17 (2010), pp. 203–210

    work page 2010

  20. [20]

    R. T. Rockafellar and R. J-B. Wets , Variational Analysis, Springer, 1998

    work page 1998

  21. [21]

    Shawe-Taylor and N

    J. Shawe-Taylor and N. Cristianini , Kernel Methods for Pattern Analysis , Cambridge University Press, 2004

    work page 2004

  22. [22]

    Usevich and I

    K. Usevich and I. Markovsky , Structured low-rank approximation as a rational function minimization, In Proceedings of the 16th IFAC Symposium on System Identification, 45 (2012), pp. 722–727

    work page 2012

  23. [23]

    Usevich and I

    K. Usevich and I. Markovsky , Variable projection methods for approximate (greatest) common divisor computations, Theoret. Comput. Sci., 681 (2017), pp. 176–198

    work page 2017

  24. [24]

    S. J. Wright, R. D. Nowak and M. A. Figueiredo , Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2019), pp. 2479–2493

    work page 2019