Source-linked AI summary
Closest Normal Matrix Found Again Using Riemannian Optimization
Vanni Noferini, Matvei Zhukov
TL;DR
The paper addresses how to compute a Frobenius-nearest normal matrix, a problem with applications in spectral computation and related areas. It formulates the task as smooth Riemannian optimization on U(n) or a flag manifold and develops a trust-region method. For generic inputs, the theory gives finitely many isolated local minimizers with distinct eigenvalues, while the algorithm improves practical performance and handles larger matrices; nonglobal minima remain possible.
Problem
Computing a Frobenius-nearest normal matrix is difficult, while common distance-from-normality bounds can be inadequate when the true relative distance is small.
Method
The paper minimizes a smooth objective on U(n) or U(n)/U(1)^n using Riemannian optimization, including a trust-region algorithm and a real-case variant.
Results
For generic inputs, the objective has finitely many nondegenerate local minimizers with distinct diagonal entries, and the trust-region method substantially improves practical performance on larger inputs.
Takeaways & Limitations
The flag-manifold formulation provides a framework for analyzing extrema and for computing nearest normal matrices with modern manifold-optimization methods.
Takeaways & Limitations
For n≥3, nonglobal local minima can occur, so the algorithm cannot guarantee the exact distance; empirical comparisons also do not settle the real-versus-complex open question.
Abstract
from arXiv · showhide
We propose an approach based on Riemannian optimization to compute a nearest normal matrix to a given one. The problem can be formulated as the minimization of a smooth function either on the manifold $U(n)$ of unitary matrices of size n or on the flag manifold $U (n)/U (1)^n$. The flag manifold is particularly suitable for theoretical analysis; we characterize the global maximum of the objective function and prove that, for generic inputs, its local minimizers are finitely many and isolated; in turn, this implies the original nearest normal matrix problem generically has finitely many local minimizers, all with distinct eigenvalues. We also develop a Riemannian trust-region method that improves substantially on classical algorithms and can handle considerably larger matrices, as well as a variant for computing the nearest real normal matrix. The paper is complemented by extensive numerical experiments.
1. Introduction.
The paper revisits the nearest normal matrix problem using Riemannian optimization on unitary or flag manifolds. It combines theoretical analysis with a trust-region algorithm intended to improve practical performance and scale.
- Motivation: The nearest normal matrix problem seeks a normal matrix closest to A in Frobenius distance, with applications including spectral computation, quantum measurement, and control.Classical distance-from-normality bounds can be inadequate when the true relative distance is small.
- Prior work: Earlier numerical solutions used Jacobi-type methods that can be interpreted as coordinate descent on the unitary manifold.The paper frames its approach as a modern Riemannian-optimization treatment of this established formulation.
- Contributions: The paper formulates the problem on U(n) or the lower-dimensional flag manifold U(n)/U(1)^n and develops theoretical and algorithmic results.The flag-manifold formulation supports analysis of objective-function extrema.
- Contributions: For generic inputs, the analysis establishes finitely many isolated local minimizers with distinct eigenvalues in the original nearest normal matrix problem.The paper also characterizes the global maximum of the corresponding objective function.
- Contributions: A Riemannian trust-region method substantially improves practical performance and handles larger inputs than previously documented algorithms.The study compares unitary and flag-manifold implementations and examines initialization behavior.
- Scope: The paper also develops a real-case variant and distinguishes its scope from contemporaneous work on the more general normal Procrustes problem.The two works were developed independently, while this paper emphasizes the flag-manifold formulation and extremum analysis.
2. Nearest normal matrix as a Riemannian optimization problem.
The nearest normal matrix problem is reduced to minimizing a smooth objective on U(n) or the flag manifold. This reduction enables Riemannian derivatives and optimization algorithms while preserving correspondence with normal-matrix minimizers.
- Objective construction: The map N(X)=X−diag(X) is the Frobenius-orthogonal projection onto matrices with zero diagonal.Diagonal matrices are characterized by diag(X)=X, while zero-diagonal matrices satisfy diag(X)=0.
- Objective construction: The objective fA(Q) is smooth on the real embedded manifold U(n) of unitary matrices.Its construction uses the off-diagonal part of Q∗AQ.
- Symmetries: Diagonal unitary and permutation transformations leave fA(Q) unchanged.Diagonal transformations alter off-diagonal entries only by phases, while permutations reorder them.
- Flag manifold: The quotient Fn=U(n)/U(1)^n, called the flag manifold, removes diagonal-unitary symmetry and has lower dimension than U(n).It parametrizes complete flags, or nested subspaces of C^n.
- Minimizer correspondence: A minimizer of fA on U(n) or Fn reconstructs a nearest normal matrix through N(Q)=Qdiag(Q∗AQ)Q∗.Global minimizers correspond directly, while local correspondence requires considering all unitary diagonalizers of a normal minimizer.
- Optimization framework: Riemannian optimization on either manifold is equivalent to finding a nearest normal matrix to A.The choice between U(n) and Fn trades reduced dimension against implementation and computational considerations.
- Algorithms: Coordinate-descent Jacobi methods inherit limitations and numerical pitfalls that motivate replacing them with Riemannian trust-region optimization.The paper derives the required derivatives and compares implementations on U(n) and Fn.
- Derivatives: The Riemannian gradient is obtained by projecting the Euclidean gradient onto the tangent space of U(n).The paper derives gradient and Hessian expressions needed for second-order Riemannian algorithms.
3. Some theoretical results on the function fA(Q).
The section characterizes the global and local behavior of fA on the flag manifold, establishing generic finiteness and nondegeneracy of local minimizers while identifying exceptional cases and the special n = 2 structure.
- For almost every A, the nearest normal matrix in Frobenius distance is unique.
- The global maximum of fA is analytically characterized and, for n ≥3, is attained at uncountably many flag-manifold points for almost every A.These maximizers nevertheless correspond to the same normal matrix (trace(A)/n)I.
- For almost every A, fA has finitely many local minimizers on the flag manifold, each with pairwise distinct diagonal entries and positive-definite Riemannian Hessian.The proof uses regular-value and Sard-type arguments to exclude a measure-zero set of inputs.
- The flag-manifold quotient is necessary for finiteness because diagonal-unitary equivalence creates uncountably many representatives on U(n), while inputs such as scalar matrices remain exceptional.
- Consequently, for almost every A, the nearest-normal-matrix problem has finitely many local minimizers, each with distinct eigenvalues and corresponding to precisely n! flag-manifold minimizers.
- 3.1. A full analytic solution for n = 2.: When n = 2, every local minimizer is global, but infinitely many local minimizers can occur for exceptional inputs; for n > 2, this property does not generalize.
4. The real case.
The real nearest-normal-matrix problem is reformulated on the orthogonal group, using block structures that represent real and complex-conjugate eigenvalue pairs. The resulting objective is handled with locally smooth Riemannian derivatives, while its piecewise structure and unresolved global-minimum guarantees remain important boundaries.
- Real normal form: Real normal matrices are orthogonally similar to block diagonal matrices with 1 × 1 blocks and 2 × 2 rotation-scaling blocks.The 2 × 2 blocks have the form [a b; −b a], encoding complex-conjugate eigenvalue pairs.
- Algorithmic design: The real algorithm preserves orthogonality while allowing the block structure to represent nonreal eigenvalues through real 2 × 2 blocks.This avoids restricting the iterates to normal matrices with only real eigenvalues.
- Optimization formulation: The real optimization minimizes the Frobenius residual over O(n), with a projection onto the appropriate block-diagonal normal structure.The projection uses 1 × 1 blocks and 2 × 2 blocks, with the residual defined from the projected transformed matrix.
- Scope and limitations: Reducing the real search space through a quotient manifold is unavailable without knowing the number of real eigenvalues of a nearest real normal matrix.Such a quotient choice is possible when the target spectrum is known, but not in the general problem considered here.
- Riemannian derivatives: On regions where the projection branch is fixed, Euclidean and Riemannian gradients and Hessians can be computed using the locally linear projection.The objective is locally smooth on an open dense subset for generic A, but is not globally differentiable.
5. Algorithmic aspects.
The experiments evaluate initialization, manifold choice, solver comparisons, local-minimum behavior, and runtime for complex and real variants of the proposed method.
- Solver comparison: The trust-region method outperformed ARC and conjugate-gradient solvers on Gaussian random matrices and perturbed normal matrices.The comparison was conducted among solvers available in the Manopt toolbox.
- Initialization: Schur initialization approximately halves average runtime compared with random and identity starts on perturbed normal matrices.The improvement was observed in numerical experiments using perturbed normal matrices.
- Initialization: Schur initialization can still miss the global-minimum basin, and it typically fails on Frank matrices.The limitation is reported despite outperforming random initialization for generic matrices.
- Choice of manifold: Neither U(n) nor the flag manifold Fn consistently outperformed the other across tested inputs; the largest average gap favoring Fn was approximately 7.4%.The comparison used Gaussian matrices, perturbed normal matrices, and similarity-transformed nilpotent Jordan blocks.
- Comparison with prior methods: The method strictly improved on prior results for three of four analytic input matrices, even at small matrix sizes.The comparison used results reported by, with GS, Ruhe, and the paper’s complex and real methods represented in Table 5.2.
- Local-minimum behavior: For Gaussian inputs, the algorithm often converged to the same local minimizer, while its probability of reaching the best observed minimizer was high when multiple minima appeared.The experiment used 500 inputs per size and 100 random starts per input.
- Empirical complexity: The experiments covered matrix sizes from 4 to 256 using 300 noisy normal inputs per size for both complex and real algorithms.Inputs were random normal matrices with 1% Gaussian noise.
- Conclusions: The paper concludes that its Riemannian method improves substantially on classical algorithms and handles considerably larger matrices, while leaving initialization reliability as future work.The conclusion also reports isolated, finite generic local minimizers and a real variant.
6. Conclusions.
The section contains acknowledgements to contributors whose comments and assistance supported the paper.
- The authors acknowledge Mark Embree, whose comments during Householder Symposium XXII inspired the paper.
- The authors also acknowledge Federico Poloni for assistance mentioned in the acknowledgements.
- The acknowledgements continue beyond the supplied passage.