Generalized matrix nearness problems II
Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim · 2026
Read Generalized matrix nearness problems II by Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30181.txt.
Introduction
Rongbiao Thomas Wang, Chi-Kwong Li and Lek-Heng Lim extend matrix nearness problems by replacing one target with three matrices in a product. They push earlier work three ways: adding an affine term, swapping matrix products for Kronecker products, and extending the Frobenius norm to any orthogonally invariant norm. Several cases admit closed-form solutions. For the rest they build an iterative algorithm with no explicit gradients, proving convergence to a global minimizer from any start, and show no Mirsky-type theorem holds for rank-constrained versions.
Catalog record
| CREATOR | Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82378 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.30181
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalized matrix nearness problems II Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim Abstract . Given a matrix A A , a matrix nearness problem seeks an X X that most closely approximates A A in the sense of minimizing ∥ A − X ∥ \lVert A-X\rVert under a variety of constraints on X X . A generalized matrix nearness problem seeks the same but with three given matrices A , B , C A,B,C and ∥ A − B X C ∥ \lVert A-BXC\rVert in place of ∥ A − X ∥ \lVert A-X\rVert . We extend previous studies of the latter problem in three directions: incorporating an affine term, replacing matrix product by Kronecker product in various manners, and generalizing Frobenius norm to any orthogonally invariant norm. We will solve several of these in closed form. For the rest, we develop an iterative algorithm that works for any Schatten norm, proving that it converges to a global minimizer regardless of the initial point. In addition, the algorithm relies purely on numerical linear algebra, and notably does not compute any explicit gradients or subgradients. Along the way, we will also show that there is no Mirsky-type theorem for rank constrained generalized matrix nearness problems. 1. Introduction This article is intended to be a sequel to [ 13 ] , in which the authors addressed the generalized matrix nearness problem : (1.1) \min_{X\in\mathcal{S}}\;\lVert A-BXC\rVert_{\scriptscriptstyle\mathsf{F}}, for given A\in\mathbb{R}^{m\times n} , B\in\mathbb{R}^{m\times p} , C\in\mathbb{R}^{q\times n} , and \lVert\,\cdot\,\rVert_{\scriptscriptstyle\mathsf{F}} the Frobenius norm. The problem was solved in [ 13 ] for a variety of common feasible sets \mathcal{S} , defined by: ➀ rank constraint: \rank(X)\leq r for a given integer r>0 ; ➁ norm constraint: \lVert X\rVert_{\scriptscriptstyle\mathsf{F}}\leq\rho for a given \rho>0 ; ➂ product constraint: FXG=H for given matrices F,G,H ; ➃ spectral constraints: X has a prescribed eigenvalue or eigenvector; ➄ symmetry constraints: X is symmetric or skew-symmetric; ➅ structure constraints: X is Toeplitz, Hankel, or circulant; ➆ positivity constraints: X is positive semidefinite, correlation, nonnegative, stochastic, or doubly stochastic. The original motivation was ➀ , which first appeared in [ 21 ] , was rediscovered in [ 9 ] , and finally given an essentially one-line solution in [ 13 ] . While one may simply treat ( 1.1 ) as a constrained optimization problem and seek a solution by applying general-purpose optimization algorithms, the methods in [ 13 ] are notable in that they solve an ostensible optimization problem ( 1.1 ) without computing a single gradient. Solutions are either given as closed-form expressions or as the results of a specialized iterative algorithm that is “zeroth order” in optimization parlance, i.e., no derivatives involved. This algorithm [ 13 , Algorithm 5] is provably convergent (i.e., yields the global minimizer X_{*} ), globally convergent (i.e., regardless of the choice of initial point X_{0} ), and linearly convergent (i.e., error \lVert X_{k}-X_{*}\rVert_{\scriptscriptstyle\mathsf{F}} decreases exponentially from one step to the next). In this article, we extend the problem ( 1.1 ) in three directions: affine: adding an affine term bx^{\scriptscriptstyle\mathsf{T}}C or Bxc^{\scriptscriptstyle\mathsf{T}} where B,C are matrices and b,c are vectors; Kronecker: replacing matrix product by Kronecker product \otimes , for example, BXC by B\otimes X\otimes C , matrix rank by Kronecker rank, eigenpairs Xw=\lambda w by partial trace \tr_{\scriptscriptstyle\mathsf{P}}(X(W\otimes I))=\lambda W ; Schatten: generalizing Frobenius norm \lVert\,\cdot\,\rVert_{\scriptscriptstyle\mathsf{F}} to an arbitrary Schatten norm. The solution methods in this article are of the same nature as those in [ 13 ] — either a closed-form solution or an iterative solution from a provably and globally convergent algorithm. Regretfully, we are unable to maintain linear convergence rate for these more complex variants of ( 1.1 ); our proposed iterative algorithm could only be guaranteed to have sublinear convergence in most cases. The best Kronecker rank- r approximation problem deserves some historical commentary. Let m=m_{1}m_{2} , n=n_{1}n_{2} . The Kronecker rank of X\in\mathbb{R}^{m\times n} is defined by \rank_{\otimes}(X)=\min\{r:X=Y_{1}\otimes Z_{1}+\dots+Y_{r}\otimes Z_{r}\}, where the minimum is taken over Y_{i}\in\mathbb{R}^{m_{1}\times n_{1}} , Z_{i}\in\mathbb{R}^{m_{2}\times n_{2}} , i=1,\dots,r . This reduces to standard matrix rank when m_{1}=m , n_{2}=n (thus n_{1}=1=m_{2} ); and so the best Kronecker rank- r approximation problem \min_{\rank_{\otimes}(X)\leq r}\lVert A-X\rVert_{\scriptscriptstyle\mathsf{F}} contains the usual best rank- r approximation problem as a special case. What is a bit surprising is that the Eckart–Young solution of the latter [ 8 ] via singular value decomposition extends nearly verbatim to the former. This fact has been rediscovered several times, for example, in [ 2 , 11 , 22 ] — the authors did not appear to be aware of earlier efforts. We will extend their works to ( 1.1 ), providing closed form solutions when BXC is replaced by B\otimes X\otimes C or (B_{1}\otimes B_{2})X(C_{1}\otimes C_{2}) ; beyond these cases, our iterative algorithm would yield the required result to machine precision. We will elaborate on these and other new contributions below. 1.1. Closed-form solutions New closed-form solutions for any matrix approximation problems are hard to come by, given that the topic has been thoroughly explored over the past ninety years since the appearance of [ 8 ] . Nevertheless we found four in the course of this work. In Section 3 , we will present these four variants of ( 1.1 ) that admit closed-form solutions. (1) Affine generalized matrix nearness: \min_{X\in\mathcal{S},\,x\in\mathbb{R}^{n}}\lVert A-BXC+dx^{\scriptscriptstyle\mathsf{T}}E\rVert_{\scriptscriptstyle\mathsf{F}}\qquad\text{or}\qquad\min_{X\in\mathcal{S},\,x\in\mathbb{R}^{m}}\lVert A-BXC+Dxe^{\scriptscriptstyle\mathsf{T}}\rVert_{\scriptscriptstyle\mathsf{F}}, for any A\in\mathbb{R}^{m\times n} , B\in\mathbb{R}^{m\times p} , C\in\mathbb{R}^{p\times n} , nonsingular D\in\mathbb{R}^{m\times m} , nonsingular E\in\mathbb{R}^{n\times n} , d\in\mathbb{R}^{m} , e\in\mathbb{R}^{n} , and any \mathcal{S}\subseteq\mathbb{R}^{p\times p} for which ( 1.1 ) has a closed-form solution. (2) Separable Kronecker product constraint: \min_{X\in\mathcal{S}}\;\lVert A-B\otimes X\otimes C\rVert_{\scriptscriptstyle\mathsf{F}}, for any A\in\mathbb{R}^{m_{1}pm_{2}\times n_{1}qn_{2}} , B\in\mathbb{R}^{m_{1}\times n_{1}} , C\in\mathbb{R}^{m_{2}\times n_{2}} , and any \mathcal{S}\subseteq\mathbb{R}^{p\times q} for which ( 1.1 ) has a closed-form solution. (3) Generalized Kronecker rank constraint: \min_{\rank_{\otimes}(X)\leq r}\lVert A-(B_{1}\otimes B_{2})X(C_{1}\otimes C_{2})\rVert_{\scriptscriptstyle\mathsf{F}}, for any A\in\mathbb{R}^{m_{1}m_{2}\times n_{1}n_{2}} , B_{1}\in\mathbb{R}^{m_{1}\times p_{1}} , B_{2}\in\mathbb{R}^{m_{2}\times p_{2}} , C_{1}\in\mathbb{R}^{q_{1}\times n_{1}} , C_{2}\in\mathbb{R}^{q_{2}\times n_{2}} . (4) Prescribed partial trace Kronecker product constraint: \min_{\tr_{\scriptscriptstyle\mathsf{P}}(X(W\otimes I))=\lambda W}\lVert A-(B_{1}\otimes B_{2})X(C_{1}\otimes C_{2})\rVert_{\scriptscriptstyle\mathsf{F}}, for any A\in\mathbb{R}^{m_{1}m_{2}\times n_{1}n_{2}} , B_{1}\in\mathbb{R}^{m_{1}\times p} , B_{2}\in\mathbb{R}^{m_{2}\times p} , C_{1}\in\mathbb{R}^{p\times n_{1}} , C_{2}\in\mathbb{R}^{p\times n_{2}} , and \lambda\in\mathbb{R} . This an analog of the prescribed eigenvalue problem in ➃ , where W plays the role of a \lambda -eigenvector. The definition of partial trace will be given in Section 3.4 . 1.2. Nonexistence of Mirsky-type result The closed-form solutions in [ 21 , 9 , 13 ] to ➀ require the Frobenius norm. One might wonder if they extend to other orthogonally invariant norms \lVert\,\cdot\,\rVert , i.e., \lVert UXV\rVert=\lVert X\rVert whenever U and V are orthogonal matrices. The underlying motivation is Mirsky’s celebrated result [ 16 ] , i.e., the Eckart–Young solution [ 8 ] for the best rank- r approximation problem \min_{\rank(X)\leq r}\lVert A-X\rVert holds universally across all orthogonally invariant norms \lVert\,\cdot\,\rVert . We show that no Mirsky-type result could possibly hold for ( 1.1 ) when B and C are not identity matrices. In fact, we will show in Section 4 that the rank constrained problem \min_{\rank(X)\leq r}\lVert A-BXC\rVert has different minimizers for different orthogonally invariant norms. 1.3. Iterative algorithm For orthogonally invariant norms other than the Frobenius norm, we neither have nor expect closed form solutions for any of the aforementioned generalized matrix