Distance to nearest skew-symmetric matrix polynomials of bounded rank

Technical Summary: Distance to Nearest Skew-Symmetric Matrix Polynomial of Bounded Rank

Problem Statement
The paper addresses a structured matrix nearness problem: given an $m \times m$ matrix polynomial $P(\lambda)$ of degree $d$ (with complex coefficients), the goal is to find a skew-symmetric matrix polynomial $S(\lambda)$ of the same degree (or at most $d$) and a specified even rank $2r$ (where $2 \le 2r \le m-1$) that minimizes the Frobenius distance to $P(\lambda)$.

This problem generalizes the well-known "distance to singularity" problem. While the distance to singularity seeks the nearest singular matrix polynomial (rank $< m$), this work targets a specific, lower rank $2r$. The authors note that for skew-symmetric matrices, the rank is always even, making the constraint of an even rank $2r$ natural. The problem is formulated as minimizing the sum of squared Frobenius norms of the differences between the coefficient matrices of $P(\lambda)$ and $S(\lambda)$.

Methodology
The proposed approach, termed GEARS (Generic Eigenstructures and Alternating direction method for Rank 2r approximation of Skew-symmetric matrix polynomials), relies on recent theoretical advances regarding the generic eigenstructures of skew-symmetric matrix polynomials.

1. Generic Factorization (Theoretical Foundation):
   The core of the method is a parametrization of the set of skew-symmetric matrix polynomials with rank at most $2r$. Building on results from [17, 18], the authors utilize Theorem 3.1, which states that the set of such polynomials is the closure of a "generic set" $G^{ss}_{d, 2r, m}$. Any element in this generic set can be factorized as:
   $$S(\lambda) = U(\lambda)V(\lambda)^T - V(\lambda)U(\lambda)^T$$
   where $U(\lambda)$ is a matrix polynomial of degree $\lfloor d/2 \rfloor$ and $V(\lambda)$ is a matrix polynomial of degree $\lceil d/2 \rceil$, both with dimensions $m \times r$.

2. Alternating Least Squares (Algorithmic Implementation):
   The minimization problem is reformulated using the vectorization operator ($\text{vec}$) and the Kronecker product. By substituting the factorization into the distance metric, the problem becomes a non-convex optimization task over the coefficients of $U(\lambda)$ and $V(\lambda)$.
   The authors solve this using an Alternating Least Squares (ALS) strategy:

   • Fix $U(\lambda)$ and solve for $V(\lambda)$ by minimizing a linear least squares problem involving a structured matrix $M(U(\lambda))$.
   • Fix the newly computed $V(\lambda)$ and solve for $U(\lambda)$ similarly.
   • Iterate until convergence. The sequence of distances is guaranteed to be monotonically non-increasing.

3. Specialization for Matrix Pencils (Degree $d=1$):
   For the specific case of matrix pencils (degree 1), the authors develop a more efficient variant, GEARS-SVD.

   • They leverage Theorem 5.3, which provides a rank-1 decomposition for skew-symmetric pencils: $S_0 - \lambda S_1 = \sum_{i=1}^r (u_i v_i^T - v_i u_i^T)$, where $u_i$ are constant vectors and $v_i$ are linear polynomial vectors.
   • This structure allows the ALS steps to be solved by directly solving smaller linear systems (via SVD and block partitioning) rather than constructing the large Kronecker product systems used in the general polynomial case. This significantly reduces computational cost.

Key Contributions

• Algorithm for Arbitrary Even Rank: Unlike previous methods that primarily addressed the distance to singularity (where rank is $m-1$ or $m-2$), this algorithm works for any prescribed even rank $2r \ge 2$.
• Theoretical Parametrization: The paper establishes a constructive parametrization of the closure of the set of skew-symmetric polynomials of bounded rank, enabling the use of factorization-based optimization.
• Efficient Solver for Pencils: The derivation of GEARS-SVD exploits the specific properties of skew-symmetric pencils to avoid large Kronecker systems, offering a substantial speedup over the general polynomial solver.
• Numerical Validation: The authors provide numerical experiments comparing GEARS and GEARS-SVD against existing methods (Riemann-Oracle and Matrix-Valued Function approaches).

Results
Numerical experiments conducted on random skew-symmetric matrix polynomials and pencils (sizes up to $50 \times 50$) demonstrate:

• Accuracy: GEARS finds solutions at distances comparable to other state-of-the-art methods.
• Singularity Quality: The solutions produced by GEARS are "more singular" (exhibiting smaller minimal singular values) than those from competing algorithms, consistent with the method's construction.
• Performance: GEARS is significantly faster than the Riemann-Oracle and MVF algorithms. For matrix pencils, GEARS-SVD outperforms the general GEARS algorithm, particularly as the matrix size increases, due to the avoidance of large Kronecker product formulations.
• Scalability: The runtime scales reasonably with matrix size, with the real-field case being approximately an order of magnitude faster than the complex case for comparable output quality.

Significance and Claims
The paper claims that its approach is distinct from and complementary to existing optimization-based strategies (like Riemann-Oracle) by leveraging the specific algebraic structure of skew-symmetric polynomials. The primary significance lies in providing a unified framework that:

1. Solves the distance-to-singularity problem as a special case.
2. Extends this capability to finding the nearest polynomial of any specified even rank.
3. Offers a computationally efficient specialized algorithm for the important case of matrix pencils.

The authors modestly note that their method is currently limited to skew-symmetric structures and that extensions to other structured classes (symmetric, palindromic, etc.) are reserved for future work. The algorithm produces a polynomial of rank exactly $2r$ (up to rounding errors) and is designed to be a practical tool for control theory, system identification, and differential-algebraic equation analysis where such structured low-rank approximations are required.