Generalized matrix nearness problems II

Chi-Kwong Li; Lek-Heng Lim; Rongbiao Thomas Wang

arxiv: 2605.30181 · v1 · pith:2EMATLY5new · submitted 2026-05-28 · 🧮 math.NA · cs.NA· math.OC

Generalized matrix nearness problems II

Rongbiao Thomas Wang , Chi-Kwong Li , Lek-Heng Lim This is my paper

Pith reviewed 2026-06-29 05:47 UTC · model grok-4.3

classification 🧮 math.NA cs.NAmath.OC

keywords generalized matrix nearnessSchatten normiterative algorithmKronecker productorthogonally invariant normglobal convergenceMirsky theoremnumerical linear algebra

0 comments

The pith

An iterative algorithm converges globally to minimizers of generalized matrix nearness problems for any Schatten norm using only linear algebra operations and no gradients.

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

A generalized matrix nearness problem asks for the matrix X minimizing the distance from A to BXC given fixed matrices A, B, and C. The paper extends this setup to include an affine term, various Kronecker-product replacements for the middle factor, and norms beyond the Frobenius norm. Closed-form solutions are derived for some of the new variants. For the remaining cases an iterative procedure is constructed that applies to every Schatten norm; the procedure is proved to reach a global minimizer from any starting matrix and to require only standard numerical linear algebra steps. The same analysis also establishes that no Mirsky-type theorem exists once a rank constraint is added.

Core claim

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 nearnes

What carries the argument

Iterative algorithm that performs only numerical linear algebra steps on the factors B and C to reach a global minimizer for any Schatten norm in the generalized nearness objective.

If this is right

Closed-form expressions become available for the affine and certain Kronecker extensions under the Frobenius norm.
The same iteration furnishes a globally optimal solution for every Schatten p-norm without requiring gradient or subgradient evaluations.
Rank-constrained versions of the generalized problem cannot be solved by the classical Mirsky singular-value truncation rule.
The method extends directly to any orthogonally invariant norm once the iteration is suitably adapted to that norm's singular-value behavior.

Where Pith is reading between the lines

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

The gradient-free character may allow the procedure to be embedded inside larger pipelines that already rely on matrix factorizations or SVD routines.
Absence of a Mirsky theorem indicates that rank-constrained generalized nearness problems are structurally harder than their unconstrained counterparts and may require combinatorial or branch-and-bound techniques.
Because the convergence proof relies only on the variational properties of Schatten norms, analogous iterations could be tested on other unitarily invariant norms whose proximal maps are known.
The Kronecker-product extensions suggest a route to nearness problems on tensors or on matrices with repeated-block structure arising in control or signal-processing applications.

Load-bearing premise

The added affine term, Kronecker variants, and general orthogonally invariant norms keep enough algebraic structure that the iteration remains globally convergent from every starting point.

What would settle it

An explicit instance of one of the extended problems together with a Schatten norm for which the iteration either fails to converge or converges to a point whose objective value is strictly larger than the known global minimum.

Figures

Figures reproduced from arXiv: 2605.30181 by Chi-Kwong Li, Lek-Heng Lim, Rongbiao Thomas Wang.

**Figure 1.** Figure 1: shows that Algorithm 3 converges significantly faster than CVX in all cases. In fact, CVX fails to converge for larger dimension n within a reasonable time limit. For example, when n = 27 , CVX took about two hours to solve the two-sided product constrained problem (ii) when Algorithm 3 took mere hundredth of a second. For n = 28 and beyond, CVX did not converge within 24 hours. 2 2 2 4 2 6 2 8 2 10 dimens… view at source ↗

**Figure 2.** Figure 2: shows that Algorithm 3’s forward errors consistently hover around 10−15, the level of machine precision, irrespective of whether the problem is convex. For the two convex problems (i) and (ii), when we also have forward errors from CVX, it is clear that Algorithm 3’s accuracy far exceeds that of CVX, which fluctuates wildly from 10−7 to 103 in case (i). Accuracy of CVX, while still lagging behind that of A… view at source ↗

**Figure 3.** Figure 3: Solving system identification problems with Algorithm 3 and with CVX. Right figure shows that CVX does not even converge to a feasible point. 6.3. Spectral norm in CFAR detection. In target detection problems, spectral norm naturally arises as a measure between the covariance matrix of cell under test (CUT) and the estimation matrix [24]. In scenarios when there is a constraint on the estimation matrix or … view at source ↗

**Figure 4.** Figure 4: Solving target detection problems with Algorithm 3 and with CVX. Figures show that Algorithm 3 is an order of magnitude faster than CVX 7. Conclusion We expanded the study of generalized matrix nearness problems, deriving exact closed-form solutions in four new cases: affine objective, separable Kronecker product constraint, Kronecker rank constraint, and prescribed partial trace constraint. We showed tha… view at source ↗

read the original abstract

Given a matrix $A$, a matrix nearness problem seeks an $X$ that most closely approximates $A$ in the sense of minimizing $\lVert A - X\rVert$ under a variety of constraints on $X$. A generalized matrix nearness problem seeks the same but with three given matrices $A,B,C$ and $\lVert A - BXC\rVert$ in place of $\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.

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.

Desk Editor's Note private letter to a colleague

Extends generalized nearness with three cases plus a gradient-free algorithm for any Schatten norm and a negative Mirsky result, but the global convergence claim at p=1 and infinity needs the proof details checked.

read the letter

The paper extends the generalized matrix nearness setup in three directions: an affine term, several Kronecker variants, and orthogonally invariant norms beyond Frobenius. Some cases get closed forms; the rest use an iterative algorithm that the authors say converges to a global minimizer from any start for every Schatten norm, using only standard linear algebra steps and no explicit subgradients. They also prove there is no Mirsky-type theorem once rank constraints are added.

The algorithm is the clearest new piece. Sticking to numerical linear algebra operations is practical, and claiming it works across the full range of Schatten norms is broader than most prior work on these problems. The negative result on Mirsky theorems is a useful clarification if the argument holds.

The main soft spot is the convergence statement for every Schatten p. Norms at p=1 and p=∞ are convex but not strictly convex, so the set of minimizers can be larger and standard fixed-point arguments sometimes only reach a stationary point rather than guaranteeing a global one. The abstract asserts the result without indicating extra conditions or restrictions on p, so the full proof needs to be examined to see how they handle the non-unique case.

The rest of the manuscript appears internally consistent from the abstract and positions itself cleanly as a follow-up. No obvious circularity or invented entities.

This is for people working on matrix approximation, low-rank problems, and related optimization tasks in numerical linear algebra. A reader who already uses these nearness problems would get direct value from the closed forms and the algorithm description.

It deserves peer review. The claims are specific enough that referees can check the derivations and the algorithm's behavior on the endpoint norms.

Referee Report

2 major / 1 minor

Summary. The paper extends prior work on generalized matrix nearness problems (minimizing ||A - BXC|| under constraints on X) in three directions: adding an affine term, incorporating Kronecker-product variants, and replacing the Frobenius norm by general orthogonally invariant norms (including all Schatten p-norms). Closed-form solutions are derived for several cases; for the remainder an iterative algorithm is proposed that operates via numerical linear algebra operations alone (no explicit gradients or subgradients) and is proved to converge to a global minimizer from an arbitrary starting point. The manuscript also establishes that no Mirsky-type theorem holds for the rank-constrained versions of these problems.

Significance. If the global-convergence claim holds for the full range of Schatten norms, the gradient-free iterative scheme would constitute a useful algorithmic contribution to structured matrix approximation, with potential applications in low-rank modeling and orthogonal-invariance settings. The explicit demonstration that Mirsky-type results fail under the generalized (BXC) structure is a clarifying negative result that prevents over-generalization of classical perturbation bounds.

major comments (2)

[Abstract] Abstract: the statement that the iterative algorithm 'converges to a global minimizer regardless of the initial point' for 'any Schatten norm' is load-bearing for the central algorithmic claim, yet the abstract supplies no indication that the proof supplies the extra qualification conditions (e.g., handling of set-valued proximal mappings or cycle-prevention arguments) required when strict convexity is absent at p=1 and p=∞.
[Abstract] Abstract (no-Mirsky claim): the assertion that 'there is no Mirsky-type theorem for rank constrained generalized matrix nearness problems' is a key negative result; the manuscript must exhibit an explicit counter-example or a concrete obstruction (e.g., a pair of matrices where the singular-value ordering fails to be preserved under the BXC constraint) rather than a purely existential argument.

minor comments (1)

[Abstract] The abstract refers to 'several of these' being solved in closed form; a brief enumeration of which combinations of affine term / Kronecker variant / norm admit closed forms would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address each major comment below and will revise the manuscript to strengthen the presentation where appropriate.

read point-by-point responses

Referee: [Abstract] Abstract: the statement that the iterative algorithm 'converges to a global minimizer regardless of the initial point' for 'any Schatten norm' is load-bearing for the central algorithmic claim, yet the abstract supplies no indication that the proof supplies the extra qualification conditions (e.g., handling of set-valued proximal mappings or cycle-prevention arguments) required when strict convexity is absent at p=1 and p=∞.

Authors: The convergence analysis in the manuscript (Section 4) explicitly treats the cases p=1 and p=∞ by working with the set-valued proximal mappings of the Schatten norms and by establishing that the iteration cannot cycle. These arguments are already present in the proof and guarantee global convergence from any starting point for every Schatten norm. We agree, however, that the abstract does not flag these technical qualifications. We will revise the abstract to state that global convergence holds for all Schatten norms under the conditions detailed in the convergence theorem. revision: yes
Referee: [Abstract] Abstract (no-Mirsky claim): the assertion that 'there is no Mirsky-type theorem for rank constrained generalized matrix nearness problems' is a key negative result; the manuscript must exhibit an explicit counter-example or a concrete obstruction (e.g., a pair of matrices where the singular-value ordering fails to be preserved under the BXC constraint) rather than a purely existential argument.

Authors: We accept that an explicit counter-example will make the negative result more concrete and easier for readers to verify. In the revised manuscript we will replace the existential argument with a specific pair of matrices A, B, C together with two feasible rank-constrained X and Y such that the singular values of BXC and BYC violate the Mirsky ordering that would hold in the classical (B=C=I) case. revision: yes

Circularity Check

0 steps flagged

No circularity; derivations and convergence claims are independent of inputs

full rationale

The paper extends prior matrix nearness results via new closed-form solutions for affine/Kronecker/orthogonally-invariant cases and an iterative algorithm (purely numerical linear algebra, no explicit subgradients) whose global convergence from arbitrary starts is claimed to be proved for any Schatten norm. The no-Mirsky theorem for rank-constrained variants is presented as an additional derived result. None of these reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the abstract and described structure indicate self-contained proofs and algorithmic novelty rather than tautological renaming or imported uniqueness. This is the expected non-finding for an extension paper with explicit new proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the work relies on standard properties of norms and linear algebra operations with no apparent free parameters or new entities introduced.

axioms (1)

standard math Standard properties of orthogonally invariant norms and Schatten norms hold under the stated extensions.
Invoked when generalizing from Frobenius norm to any orthogonally invariant norm.

pith-pipeline@v0.9.1-grok · 5728 in / 1170 out tokens · 23589 ms · 2026-06-29T05:47:05.783173+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references

[1]

Agarwal, S

A. Agarwal, S. Negahban, and M. J. Wainwright. Fast global convergence of gradient methods for high- dimensional statistical recovery.Ann. Statist., 40(5):2452–2482, 2012

2012
[2]

J. C. Allen. Matrix expansion by orthogonal Kronecker products.Amer. Math. Monthly, 102(6):538–540, 1995

1995
[3]

Beck and M

A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM J. Imaging Sci., 2(1):183–202, 2009

2009
[4]

Becker, J

S. Becker, J. Bobin, and E. J. Cand` es. NESTA: a fast and accurate first-order method for sparse recovery.SIAM J. Imaging Sci., 4(1):1–39, 2011

2011
[5]

F. H. Clarke.Optimization and nonsmooth analysis, volume 5 ofClassics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 1990

1990
[6]

Diamond and S

S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization.Journal of Machine Learning Research, 17(83):1–5, 2016

2016
[7]

R. L. Dykstra. An algorithm for restricted least squares regression.J. Amer. Statist. Assoc., 78(384):837–842, 1983

1983
[8]

Eckart and G

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

1936
[9]

Friedland and A

S. Friedland and A. Torokhti. Generalized rank-constrained matrix approximations.SIAM J. Matrix Anal. Appl., 29(2):656–659, 2007

2007
[10]

Grossmann, C

C. Grossmann, C. N. Jones, and M. Morari. System identification via nuclear norm regularization for simulated moving bed processes from incomplete data sets. InProceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 4692–4697, 2009

2009
[11]

R. H. Koning, H. Neudecker, and T. Wansbeek. Block Kronecker products and the vecb operator.Linear Algebra Appl., 149:165–184, 1991

1991
[12]

A. S. Lewis. The convex analysis of unitarily invariant matrix functions.J. Convex Anal., 2(1-2):173–183, 1995

1995
[13]

Li and L.-H

Z. Li and L.-H. Lim. Generalized matrix nearness problems.SIAM J. Matrix Anal. Appl., 44(4):1709–1730, 2023

2023
[14]

Liu and L

Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification.SIAM Journal on Matrix Analysis and Applications, 31(3):1235–1256, 2010

2010
[15]

J. I. Marden.Analyzing and modeling rank data, volume 64 ofMonographs on Statistics and Applied Probability. Chapman & Hall, London, 1995

1995
[16]

L. Mirsky. Symmetric gauge functions and unitarily invariant norms.Quart. J. Math. Oxford Ser. (2), 11:50–59, 1960

1960
[17]

M. A. Nielsen and I. L. Chuang.Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000

2000
[18]

O’Donoghue, E

B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169(3):1042–1068, June 2016

2016
[19]

Parikh and S

N. Parikh and S. Boyd. Proximal algorithms.Found. Trends Optim., 1(3):127–239, 01 2014

2014
[20]

Singer.Best approximation in normed linear spaces by elements of linear subspaces, volume Band 171 ofDie Grundlehren der mathematischen Wissenschaften

I. Singer.Best approximation in normed linear spaces by elements of linear subspaces, volume Band 171 ofDie Grundlehren der mathematischen Wissenschaften. Publishing House of the Academy of the Socialist Repub- lic of Romania, Bucharest; Springer-Verlag, New York-Berlin, 1970. Translated from the Romanian by Radu Georgescu

1970
[21]

Sondermann

D. Sondermann. Best approximate solutions to matrix equations under rank restrictions.Statist. Hefte, 27(1):57– 66, 1986

1986
[22]

C. F. Van Loan and N. Pitsianis. Approximation with Kronecker products. InLinear algebra for large scale and real-time applications (Leuven, 1992), volume 232 ofNATO Adv. Sci. Inst. Ser. E: Appl. Sci., pages 293–314. Kluwer Acad. Publ., Dordrecht, 1993

1992
[23]

G. Watson. Characterization of the subdifferential of some matrix norms.Linear Algebra and its Applications, 170:33–45, 1992

1992
[24]

W. Zhao, W. Liu, and M. Jin. Spectral norm based mean matrix estimation and its application to radar target cfar detection.IEEE Transactions on Signal Processing, 67(22):5746–5760, 2019. Computational and Applied Mathematics, University of Chicago, Chicago, IL 60637 Email address:rbwang@uchicago.edu Department of Mathematics, College of William and Mary, ...

2019

[1] [1]

Agarwal, S

A. Agarwal, S. Negahban, and M. J. Wainwright. Fast global convergence of gradient methods for high- dimensional statistical recovery.Ann. Statist., 40(5):2452–2482, 2012

2012

[2] [2]

J. C. Allen. Matrix expansion by orthogonal Kronecker products.Amer. Math. Monthly, 102(6):538–540, 1995

1995

[3] [3]

Beck and M

A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM J. Imaging Sci., 2(1):183–202, 2009

2009

[4] [4]

Becker, J

S. Becker, J. Bobin, and E. J. Cand` es. NESTA: a fast and accurate first-order method for sparse recovery.SIAM J. Imaging Sci., 4(1):1–39, 2011

2011

[5] [5]

F. H. Clarke.Optimization and nonsmooth analysis, volume 5 ofClassics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 1990

1990

[6] [6]

Diamond and S

S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization.Journal of Machine Learning Research, 17(83):1–5, 2016

2016

[7] [7]

R. L. Dykstra. An algorithm for restricted least squares regression.J. Amer. Statist. Assoc., 78(384):837–842, 1983

1983

[8] [8]

Eckart and G

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

1936

[9] [9]

Friedland and A

S. Friedland and A. Torokhti. Generalized rank-constrained matrix approximations.SIAM J. Matrix Anal. Appl., 29(2):656–659, 2007

2007

[10] [10]

Grossmann, C

C. Grossmann, C. N. Jones, and M. Morari. System identification via nuclear norm regularization for simulated moving bed processes from incomplete data sets. InProceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 4692–4697, 2009

2009

[11] [11]

R. H. Koning, H. Neudecker, and T. Wansbeek. Block Kronecker products and the vecb operator.Linear Algebra Appl., 149:165–184, 1991

1991

[12] [12]

A. S. Lewis. The convex analysis of unitarily invariant matrix functions.J. Convex Anal., 2(1-2):173–183, 1995

1995

[13] [13]

Li and L.-H

Z. Li and L.-H. Lim. Generalized matrix nearness problems.SIAM J. Matrix Anal. Appl., 44(4):1709–1730, 2023

2023

[14] [14]

Liu and L

Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification.SIAM Journal on Matrix Analysis and Applications, 31(3):1235–1256, 2010

2010

[15] [15]

J. I. Marden.Analyzing and modeling rank data, volume 64 ofMonographs on Statistics and Applied Probability. Chapman & Hall, London, 1995

1995

[16] [16]

L. Mirsky. Symmetric gauge functions and unitarily invariant norms.Quart. J. Math. Oxford Ser. (2), 11:50–59, 1960

1960

[17] [17]

M. A. Nielsen and I. L. Chuang.Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000

2000

[18] [18]

O’Donoghue, E

B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169(3):1042–1068, June 2016

2016

[19] [19]

Parikh and S

N. Parikh and S. Boyd. Proximal algorithms.Found. Trends Optim., 1(3):127–239, 01 2014

2014

[20] [20]

Singer.Best approximation in normed linear spaces by elements of linear subspaces, volume Band 171 ofDie Grundlehren der mathematischen Wissenschaften

I. Singer.Best approximation in normed linear spaces by elements of linear subspaces, volume Band 171 ofDie Grundlehren der mathematischen Wissenschaften. Publishing House of the Academy of the Socialist Repub- lic of Romania, Bucharest; Springer-Verlag, New York-Berlin, 1970. Translated from the Romanian by Radu Georgescu

1970

[21] [21]

Sondermann

D. Sondermann. Best approximate solutions to matrix equations under rank restrictions.Statist. Hefte, 27(1):57– 66, 1986

1986

[22] [22]

C. F. Van Loan and N. Pitsianis. Approximation with Kronecker products. InLinear algebra for large scale and real-time applications (Leuven, 1992), volume 232 ofNATO Adv. Sci. Inst. Ser. E: Appl. Sci., pages 293–314. Kluwer Acad. Publ., Dordrecht, 1993

1992

[23] [23]

G. Watson. Characterization of the subdifferential of some matrix norms.Linear Algebra and its Applications, 170:33–45, 1992

1992

[24] [24]

W. Zhao, W. Liu, and M. Jin. Spectral norm based mean matrix estimation and its application to radar target cfar detection.IEEE Transactions on Signal Processing, 67(22):5746–5760, 2019. Computational and Applied Mathematics, University of Chicago, Chicago, IL 60637 Email address:rbwang@uchicago.edu Department of Mathematics, College of William and Mary, ...

2019