Properties of best approximations with respect to Ky Fan $p$-$k$ norm, and strict spectral approximants of a matrix

This paper addresses open questions regarding strict spectral approximants by computing the subdifferential of the Ky Fan $p$-$k$ norm to establish characterizations for best approximations and derive necessary and sufficient conditions for $\varepsilon$-orthogonality.

The Gist

Imagine you are trying to fit a square peg into a round hole, but you have a whole toolbox of different "shapes" (mathematical norms) to measure how well the peg fits. This paper is about finding the perfect fit for a complex object (a matrix) inside a specific, restricted space, using a very sophisticated measuring tape called the Ky Fan p-k norm.

Here is a breakdown of the paper's ideas using everyday analogies:

1. The Big Picture: The "Best Fit" Problem

Imagine you have a messy, complicated sculpture (a Matrix $A$). You want to simplify it by placing it inside a specific "room" or "subspace" (a set of allowed shapes, called $\mathcal{M}$).

Your goal is to find a simplified version of the sculpture (a Best Approximation $Y$) that lives in that room and is as close as possible to the original.

• The Problem: How do you define "close"? In math, we use "norms" (rulers).
• The Ruler: This paper focuses on a special ruler called the Ky Fan p-k norm. Think of this ruler not just measuring the total size of the sculpture, but specifically measuring its top $k$ most prominent features (like its largest bumps or spikes).

2. The "Strict Spectral" Mystery

The authors are trying to solve a puzzle left by a previous mathematician (K. Zi˛etak).

• The Puzzle: If you use a ruler that gets more and more obsessed with the single biggest feature of your sculpture (as you turn a dial called $p$ to infinity), does your "best fit" eventually settle on a specific, unique "Strict Spectral Approximation"?
• The Conjecture: It was guessed that yes, as you zoom in on the biggest feature, the best fit converges to this unique "Strict Spectral" version.
• The Catch: The previous attempt to prove this failed because the authors didn't fully understand the "shape" of the Ky Fan ruler itself. They needed to know exactly how the ruler behaves when you push it.

3. The Secret Weapon: The "Subdifferential" (The Ruler's Fingerprints)

To solve the puzzle, the authors had to map the Subdifferential of the Ky Fan norm.

• The Analogy: Imagine the ruler isn't a smooth stick, but a jagged, multi-faceted gem. If you push the ruler against a wall, it touches at a specific point. The "subdifferential" is the list of all possible directions the ruler could be "pushing" at that exact moment.
• Why it matters: In math, if you want to find the lowest point in a valley (the best approximation), you look for where the "push" of the ruler balances out to zero. By calculating these "fingerprints" (the subdifferential), the authors could finally see exactly how the ruler behaves.

4. Key Discoveries

A. The "Orthogonality" Dance

The paper figures out when two objects are "perpendicular" (orthogonal) according to this special ruler.

• Normal Orthogonality: Like two lines crossing at 90 degrees.
• Ky Fan Orthogonality: This is trickier. It's like saying, "If I add a little bit of this new shape to my sculpture, the top $k$ biggest bumps won't get any bigger."
• The Result: The authors gave a precise recipe (using vectors and singular values) to check if two matrices are perpendicular under this specific ruler.

B. The "Unique Fit" Guarantee

The authors proved that if the "room" you are trying to fit into is very small (specifically, a one-dimensional line spanned by a matrix with high rank), there is only one perfect fit.

• Analogy: If you are trying to fit a complex shape onto a single tightrope, there's only one spot where it balances perfectly. If the rope is too loose or the shape too weird, you might have multiple balancing spots. This paper proves that under certain conditions, the balance point is unique.

C. The Conjecture: Does it Converge?

The paper tackles the big question: As the ruler focuses more intensely on the biggest feature (as $p \to \infty$), does the best fit become the "Strict Spectral" fit?

• The Answer: It's complicated!
  • Yes, sometimes: If the "room" is simple (like a 2x2 or 2xN matrix space), the answer is YES. The best fit smoothly slides into the Strict Spectral position.
  • No, not always: The authors found a counter-example (a specific 3x3 matrix setup) where the "Strict Spectral" guess was actually wrong. The best fit doesn't always settle on the expected spot. This disproves the idea that the previous conjecture was true in every case.

5. Why Should You Care?

This isn't just abstract math; it's about optimization.

• Real World: This kind of math is used in signal processing, quantum physics, and machine learning. When engineers try to compress data or filter out noise, they are essentially looking for the "best approximation" of a complex signal.
• The Takeaway: This paper provides the "instruction manual" for using a very powerful, specialized tool (the Ky Fan p-k norm). It tells engineers and scientists exactly when they can trust their tools to give a unique answer and when they need to be careful because the answer might be tricky.

Summary in One Sentence

The authors mapped the hidden "fingerprints" of a complex mathematical ruler to solve a puzzle about finding the perfect fit for data, proving that while the ruler works perfectly in simple cases, it can behave unexpectedly in more complex scenarios.

Technical Summary

Here is a detailed technical summary of the paper "Properties of Best Approximations with Respect to Ky Fan p-k Norm, and Strict Spectral Approximants of a Matrix" by Priyanka Grover and Krishna Kumar Gupta.

1. Problem Statement

The paper addresses open questions regarding the convergence of best matrix approximations in various norms, specifically focusing on the relationship between $c_p$-approximations (Schatten $p$-norms) and strict spectral approximations (lexicographically minimal singular value vectors).

• Context: In matrix approximation theory, given a matrix $A$ and a subspace $M$, a "best approximation" $Y \in M$ minimizes $\|A - Y\|$.
• The Conjecture: A conjecture by Zi˛etak [36] posits that as $p \to \infty$, the unique best approximation $Y_p$ in the Schatten $p$-norm ($c_p$-norm) converges to the strict spectral approximation $Y^{(st)}$. The strict spectral approximation is defined as the element in $M$ that minimizes the vector of singular values of the error matrix $A-Y$ under lexicographic ordering.
• The Gap: Previous attempts to prove this conjecture were incomplete due to a lack of detailed characterization of best approximations with respect to the Ky Fan $p$-$k$ norms (a generalization of the Ky Fan $k$-norm and the spectral norm). Specifically, the subdifferential structure of these norms was not sufficiently explicit to derive necessary and sufficient conditions for optimality.

2. Methodology

The authors employ tools from convex analysis, matrix theory, and subdifferential calculus to resolve the problem.

• Subdifferential Computation: The core methodological contribution is the explicit computation of the subdifferential set ($\partial \|\cdot\|_{(p,k)}$) for the Ky Fan $p$-$k$ norm for $p \ge 2$.
  • They utilize the representation of the Ky Fan $p$-$k$ norm as a maximization over unitary matrices.
  • They apply Fréchet differentiability results for matrix functions (specifically involving the map $X \mapsto (X^*X)^{p/2}$) and the chain rule.
  • They use a theorem by Rockafellar regarding the subdifferential of the supremum of a family of convex functions.
• Characterization of Orthogonality: Using the computed subdifferentials, the authors derive necessary and sufficient conditions for:
  • $\epsilon$-Birkhoff-James orthogonality (approximate orthogonality).
  • Exact Birkhoff-James orthogonality to a subspace.
  • Norm parallelism.
• Convergence Analysis: They analyze the behavior of the error matrix $R_p = A - Y_p$ as $p \to \infty$. By examining the singular values $\sigma_i(R_p)$ and utilizing the properties of the subdifferential, they investigate the convergence of $Y_p$ to $Y^{(st)}$.
• Counter-Example Construction: To address the limitations of previous proofs, they construct a specific counter-example to a sub-conjecture regarding the selection of minimal elements in the lexicographic ordering.

3. Key Contributions and Results

A. Explicit Subdifferential of Ky Fan $p$-$k$ Norms (Theorem 2.4)

The authors provide a closed-form expression for the subdifferential of the Ky Fan $p$-$k$ norm for $p \ge 2$. For a non-zero matrix $A$:
$$\partial \|A\|_{(p,k)} = \text{conv} \left\{ \frac{1}{\|A\|_{(p,k)}^{p-1}} A(A^*A)^{\frac{p-2}{2}} \sum_{i=1}^k v_i v_i^* \right\}$$
where $\{v_1, \dots, v_k\}$ are orthonormal right singular vectors of $A$ corresponding to the largest $k$ singular values.

• Significance: This explicit form allows for the derivation of optimality conditions that were previously unavailable. It shows that the subdifferential is a singleton if the $k$-th singular value is strictly greater than the $(k+1)$-th.

B. Characterization of Approximate and Exact Orthogonality

The paper derives conditions for a matrix $A$ to be $\epsilon$-orthogonal to a matrix $B$ (or a subspace $M$) with respect to the Ky Fan $p$-$k$ norm.

• Result: $A \perp_\epsilon B$ if and only if there exist orthonormal vectors $v_i$ (associated with the top singular values of $A$) and a scalar $z_0$ with $|z_0| \le 1$ such that a specific linear combination involving the inner products of $A$ and $B$ vanishes.
• Application: This leads to a characterization of Birkhoff-James orthogonality (where $\epsilon=0$) and norm parallelism.

C. Uniqueness of Best Approximations (Theorem 3.1)

The authors prove that if the rank of the direction matrix $X$ satisfies $\text{rank}(X) > n - k$, the best approximation to a one-dimensional subspace $\text{span}\{X\}$ in the Ky Fan $p$-$k$ norm is unique. This uniqueness is crucial for analyzing convergence properties.

D. Convergence to Strict Spectral Approximant

The paper makes significant progress on the conjecture $Y_p \to Y^{(st)}$ as $p \to \infty$:

1. Partial Proof: The convergence is proven to hold in special cases:
   • When the subspace $M$ is one-dimensional with full rank.
   • When the multiplicity of the largest singular value of the error matrix is equal to the dimension ($s_1 = n_0$).
   • For matrices in spaces $M_{2 \times n}(\mathbb{C})$ and $M_{m \times 2}(\mathbb{C})$.
2. Refutation of a Sub-conjecture: The authors disprove a specific assumption made in [36] that the "minimal" element in the lexicographic ordering of error matrices (denoted $R_{min}$) could always be used to construct a better approximation. They provide a counter-example in $M_{3 \times 3}(\mathbb{C})$ showing that $R_{min}$ does not necessarily satisfy the required inequality conditions to force convergence in the general case.

E. Characterization of Best Approximants (Theorem 3.9)

A new characterization is provided for best approximations $R_{(p,k)}$ in the Ky Fan $p$-$k$ norm. If the $k$-th singular value of the error is strictly greater than the $(k+1)$-th, then the first $k$ singular values of any best approximation are identical. This implies a strong structural rigidity in the set of best approximations under these conditions.

4. Significance

• Theoretical Advancement: The paper fills a critical gap in the theory of matrix approximation by providing the missing subdifferential calculus for Ky Fan $p$-$k$ norms. This bridges the gap between the well-understood $c_p$-norms and the more complex spectral/lexicographic approximations.
• Resolution of Open Problems: It answers specific questions raised by Zi˛etak regarding the properties of best approximations and the conditions for $\epsilon$-orthogonality.
• Clarification of Convergence: While the general conjecture $Y_p \to Y^{(st)}$ remains open for arbitrary subspaces, the paper establishes its validity for important special cases (low dimensions, specific rank conditions) and clarifies why previous proof attempts failed (by disproving the assumption about $R_{min}$).
• Methodological Impact: The techniques used (combining Fréchet derivatives of matrix functions with convex analysis) offer a robust framework for studying other unitarily invariant norms and their approximation properties.

In summary, this paper provides the necessary analytical tools (subdifferentials) to study best approximations in Ky Fan $p$-$k$ norms, characterizes orthogonality in this setting, and makes substantial progress toward understanding the convergence of $p$-norm approximations to strict spectral approximants, while simultaneously correcting misconceptions in the existing literature.