🔢 mathematics

Generalized matrix nearness problems II

This paper extends generalized matrix nearness problems by incorporating affine terms, Kronecker products, and arbitrary orthogonally invariant norms, providing closed-form solutions for specific cases and a gradient-free iterative algorithm that guarantees global convergence for the remainder, while also demonstrating the non-existence of a Mirsky-type theorem for rank-constrained variants.

Original authors: Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to fix a blurry, distorted photograph. You know the original image was perfect, but now it's been stretched, squashed, or mixed with some noise. Your goal is to find the "best" version of that original image that fits the distorted data you have. In the world of mathematics, this is called a Matrix Nearness Problem.

This paper is a sequel to a previous study by the same authors. Think of the first paper as learning how to fix a photo that was just slightly warped. This new paper tackles much more complex distortions and introduces new tools to fix them, all without using the heavy, slow machinery usually required for such tasks.

Here is a breakdown of what they did, using simple analogies:

1. The New Distortions (The "What")

In the old problem, you were trying to find a matrix $X$ to fix the equation $A \approx X$ . It was like trying to find a clean photo that looks like a blurry one.

In this new paper, the equation is much more complicated: $A \approx BXC$ .

The Analogy: Imagine you aren't just looking for a photo; you are looking for a photo that has been run through a specific filter ( $B$ ), then a specific lens ( $C$ ), and maybe even had a sticker added to it (an "affine term").
The Twist: The authors also introduced Kronecker products. If a normal matrix is a single photo, a Kronecker product is like a photo made of smaller, repeating tiles. They figured out how to fix these "tiled" photos too, even when the tiles have specific rules about how they can be arranged (like a puzzle with a fixed number of pieces).

2. The New Rules (The "Constraints")

Usually, when you try to fix a photo, you might have rules: "The photo must be black and white," or "The photo must be a perfect square," or "The photo must only have 5 distinct colors."

The authors showed how to solve their complex equation while obeying all sorts of these rules:

Rank constraints: The image must be simple (low rank).
Symmetry: The image must look the same if you flip it.
Positivity: All the numbers in the image must be positive (like light intensity).
New Rules: They even added rules for "partial traces" (a concept from quantum physics, like measuring only part of a system) and specific "eigenvalue" rules (like forcing a specific pattern to exist in the image).

3. The Big Surprise: One Size Does NOT Fit All

In the past, mathematicians believed that if you found the best solution using one type of "ruler" (the Frobenius norm, which is like measuring total pixel error), that same solution would be the best for any other ruler you used. This was called the Mirsky Theorem.

The authors proved this is false for their complex problems.

The Analogy: Imagine you are trying to fit a suitcase into a car trunk. If you measure the suitcase by its total volume, you get one size. If you measure it by its longest side, you get a different size. For simple problems, the "best fit" is the same regardless of how you measure. But for these complex, distorted problems, the "best fit" changes depending on which ruler you use. There is no single "magic solution" that works for every way of measuring error.

4. The New Tool: The "Zeroth-Order" Algorithm

Since there is no single magic solution and the problems are too hard to solve with a simple formula (closed-form) in most cases, you usually need a computer to guess and check.

The Old Way: Most optimization algorithms are like a hiker trying to find the bottom of a valley. They look at the slope (the gradient) to decide which way to step. This requires calculating complex derivatives, which is slow and computationally expensive.
The Authors' Way: They developed an algorithm (Algorithm 3) that is "zeroth-order."
- The Analogy: Instead of looking at the slope, this algorithm is like a blindfolded hiker who knows the shape of the valley perfectly. They don't need to feel the ground to know which way is down; they just take a step based on a pre-calculated map.
- The Benefit: It doesn't calculate any gradients or derivatives. It relies purely on standard linear algebra (like breaking down matrices into their core parts).
- The Result: It is incredibly fast and accurate. In their tests, it was orders of magnitude faster than standard software (like CVX) and could solve problems that the standard software couldn't even touch (like measuring error with a "Schatten 3/2-norm," which is a weird, non-standard ruler that other software doesn't understand).

5. Real-World Tests

The authors didn't just do math on paper; they tested their tool on real-world scenarios:

System Identification: Trying to figure out how a machine works based on its inputs and outputs. Their tool found the answer quickly and stayed within the safety limits, while standard software often failed to find a valid answer at all.
Target Detection: Trying to spot a target (like a radar signal) amidst noise. Their tool was 10 times faster than the competition.

Summary

This paper is about taking a very difficult mathematical puzzle (fixing complex, distorted data with strict rules) and solving it with a clever, lightweight tool.

They found exact solutions for four specific, tricky variations of the puzzle.
They proved that for the rest, you can't use a "one-size-fits-all" solution.
They built a new, fast algorithm that doesn't need to calculate slopes (gradients) to find the best answer.
They showed that this new tool is faster and more accurate than the heavy, standard tools everyone else uses, even for problems those tools can't solve.

It's a reminder that sometimes, old-school, clever math tricks (linear algebra) work better than modern, heavy-duty optimization software.

Technical Summary: Generalized Matrix Nearness Problems II

Problem Definition

This paper extends the study of generalized matrix nearness problems, originally addressed in [13]. The fundamental problem seeks a matrix $X$ that minimizes the distance to a given matrix $A$ under specific constraints. The generalized form considered here involves three given matrices $A, B, C$ and minimizes the objective function:
$\min_{X \in S} \|A - BXC\|$
where $S$ represents a feasible set defined by various constraints (e.g., rank, norm, symmetry, structure, positivity). The paper specifically investigates three extensions to the standard Frobenius norm formulation ( $\|\cdot\|_F$ ) found in [13]:

Affine Terms: Incorporating affine terms such as $dx^TE$ or $Dxe^T$ into the objective.
Kronecker Products: Replacing standard matrix products with Kronecker products (e.g., $B \otimes X \otimes C$ ) and generalizing rank constraints to Kronecker rank.
Schatten Norms: Generalizing the Frobenius norm to arbitrary orthogonally invariant norms, specifically Schatten $p$ -norms ( $\|\cdot\|_{\sigma,p}$ ).

Methodology

The paper employs a dual approach: deriving closed-form solutions for specific cases and developing a zeroth-order iterative algorithm for the general case.

1. Closed-Form Solutions

The authors identify four specific variants of the problem that admit closed-form solutions, extending the results of [13]:

Affine Generalized Nearness: Problems involving terms like $\|A - BXC + Dxe^T\|_F$ . These are transformed into standard generalized nearness problems using projection operators (Proposition 3.2).
Separable Kronecker Product: Minimizing $\|A - B \otimes X \otimes C\|_F$ . This is solved by introducing a rearrangement operator $R$ that transforms the Kronecker structure into a standard matrix nearness problem (Proposition 3.3).
Generalized Kronecker Rank: Minimizing $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ subject to $\text{rank}_\otimes(X) \le r$ . This reduces to a standard rank-constrained problem via the rearrangement operator and singular value decomposition (SVD) properties of Kronecker products (Proposition 3.4, Algorithm 1).
Prescribed Partial Trace: Minimizing $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ subject to a partial trace constraint $\text{tr}_P(X(W \otimes I)) = \lambda W$ . This is reduced to a prescribed eigenvalue problem or a rank-constrained problem (Proposition 3.5, Corollary 3.6).

2. Non-Existence of Mirsky-Type Results

The paper investigates whether the Eckart–Young–Mirsky theorem (which states that the best rank- $r$ approximation is independent of the orthogonally invariant norm used) extends to the generalized problem $\min_{\text{rank}(X) \le r} \|A - BXC\|$ .

Result: The authors prove that no Mirsky-type result holds when $B$ and $C$ are not identity matrices.
Evidence: Through a counterexample (Example 4.2), they demonstrate that the minimizer for the rank-constrained generalized problem depends on the specific Schatten norm ( $p=1, 2, \infty$ ) chosen. This contrasts with the standard rank approximation problem where the solution is universal across all orthogonally invariant norms.

3. Iterative Algorithm (Algorithm 3)

For cases where closed-form solutions do not exist (specifically for general Schatten norms and complex constraints), the authors propose an iterative algorithm based on Dykstra's projection method (Algorithm 2), specialized for Schatten norms (Algorithm 3).

Mechanism: The algorithm alternates between two steps:
1. $X$ -update: Solves a generalized matrix nearness problem in the Frobenius norm (using methods from [13] or the closed-form solutions derived in Section 3).
2. $Y$ -update: Solves a proximal operator problem for the Schatten norm $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$ . The authors derive explicit closed-form updates for the singular values of $Y$ for $p=1$ (nuclear norm), $p=\infty$ (spectral norm), and general $p \in (1, \infty)$ (Lemmas 5.5–5.7).
Key Feature: The algorithm is zeroth-order; it does not compute explicit gradients or subgradients. It relies purely on numerical linear algebra operations (SVDs and matrix multiplications).
Convergence: The algorithm is proven to converge to a global minimizer from any initial point. The convergence rate is sublinear (due to the lack of strong convexity in Schatten norms for $p \neq 2$ ), though numerical experiments suggest near-linear behavior in practice.

Key Results

Closed-Form Expansions: The paper provides explicit solutions for affine, separable Kronecker, Kronecker rank, and partial trace variants of the generalized nearness problem.
Theoretical Limitation: It establishes that the universality of the solution across different orthogonally invariant norms (Mirsky's theorem) breaks down in the presence of non-identity multipliers $B$ and $C$ .
Algorithmic Performance:
- Speed: In numerical experiments (Section 6), Algorithm 3 significantly outperforms general-purpose convex optimization solvers (specifically CVX with the SCS solver). For large dimensions, CVX often fails to converge within reasonable time limits, whereas Algorithm 3 converges rapidly.
- Accuracy: Algorithm 3 achieves machine precision ( $\approx 10^{-15}$ ) in forward error, whereas CVX exhibits fluctuating errors (ranging from $10^{-7}$ to $10^3$ ) and often fails to satisfy constraints (e.g., in system identification tasks).
- Versatility: The algorithm successfully handles non-standard convex objectives (e.g., Schatten $3/2$ -norm) and non-convex constraints (e.g., rank constraints, prescribed eigenvalues) that are inaccessible to standard solvers like CVX.

Significance and Claims

The paper claims to advance the field of matrix nearness problems by:

Extending Solvability: Providing closed-form solutions for new classes of problems involving affine terms and Kronecker structures.
Clarifying Theoretical Boundaries: Demonstrating the limitations of extending classical approximation theorems (Mirsky) to generalized settings.
Offering a Robust Alternative: Proposing an iterative algorithm that is globally convergent, gradient-free, and computationally superior to general-purpose solvers.
Highlighting Structural Exploitation: The authors emphasize that exploiting specific matrix structures via numerical linear algebra (as done in [13] and this work) yields better performance and broader applicability (including non-convex cases) than relying solely on general convex optimization frameworks.

The work is presented as a sequel to [13], maintaining the philosophy of solving optimization problems without derivative computations, thereby leveraging the rich structure of matrix spaces.