Submodular spectral functions of principal submatrices of an hermitian matrix

Sergei Friedland, Stéphane GaubertarXiv 2010 · arXiv · OpenReview

Abstract

We extend the multiplicative submodularity of the principal determinants of a nonnegative definite hermitian matrix to other spectral functions. We show that if $f$ is the primitive of a function that is operator monotone on an interval containing the spectrum of a hermitian matrix $A$, then the function $I\mapsto {\rm tr} f(A[I])$ is supermodular, meaning that ${\rm tr} f(A[I]) + {\rm tr} f(A[J]) \leq {\rm tr} f(A[I\cup J]) + {\rm tr} f(A[I\cap J])$, where $A[I]$ denotes the $I\times I$ principal submatrix of $A$. We discuss extensions to self-adjoint operators on infinite dimensional Hilbert space and to $M$-matrices. We discuss an application to CUR approximation of nonnegative hermitian matrices.

Introduction

In data science and combinatorial optimization, selecting a representative subset of data from a massive dataset often leads to a "combinatorial explosion." For a matrix of size $m \times m$, choosing the optimal $k$ rows involves evaluating $\binom{m}{k}$ possibilities, a task that quickly becomes computationally intractable.

Historically, the determinant of a positive definite matrix has been a primary tool for this task because it is log-submodular. This property allows for the use of greedy algorithms—selecting the best item iteratively—while guaranteeing that the result is within a factor of $(1 - 1/e)$ of the global optimum. This paper generalizes this "magic" property to a broader class of spectral functions, providing a theoretical foundation for efficient optimization across various matrix-based problems.

Theoretical Framework: Operator Monotonicity

The core of the research relies on Loewner’s theory of operator monotone functions. A function $f$ is considered operator monotone if it preserves the semi-definite ordering of matrices; that is, if $A \le B$ implies $f(A) \le f(B)$.

The authors establish a fundamental "Primitive Rule": if a function $f$ is the primitive (the integral) of an operator monotone function, then the trace of $f$ applied to a principal submatrix, $I \mapsto \text{tr } f(A[I])$, is supermodular. By utilizing integral representations, the authors decompose complex spectral functions into simpler components to prove these properties rigorously.

Key Insights and Spectral Properties

The paper identifies specific thresholds where spectral functions transition between submodularity and supermodularity, particularly for power functions and entropy:

  • The Power of $p$: For the power function $t^p$, the behavior is determined by the exponent:
  • If $0 \le p \le 1$, the function is submodular.
  • If $1 \le p \le 2$, the function is supermodular.
  • Outside these ranges (e.g., $p > 2$ or $p < 0$), these properties generally fail to hold.
  • Von Neumann Entropy: The paper proves that entropy-related functions (such as $t \log t$) are submodular. This has significant implications for experimental design and quantum information theory, where entropy is a standard measure of uncertainty or information content.

Generalizations and Applications

The findings are not limited to standard Hermitian matrices. The authors successfully extend their proofs to:

  1. M-matrices: Matrices with non-positive off-diagonal entries, which are prevalent in economics and probability theory.
  2. Infinite-Dimensional Spaces: The results hold for self-adjoint operators on Hilbert spaces, broadening the applicability to functional analysis.

CUR Approximation

A practical application discussed is the CUR approximation, where a matrix $A$ is approximated by a subset of its actual rows ($C$) and columns ($R$). The authors demonstrate that if the spectral function used to measure error is non-decreasing, a greedy selection strategy yields a provable approximation factor. Proposition 12 in the paper provides specific error bounds that relate the greedy result to the theoretical optimal subset.

Limitations

While the results expand the toolkit for matrix optimization, they also define clear boundaries:

  • Tightness of Bounds: Counter-examples in Section 6 show that supermodularity is lost for $p > 2$, meaning the greedy shortcut cannot be applied universally to all physics or data problems.
  • Scaling Requirements: For certain guarantees (like those involving determinants), the matrix must be appropriately scaled (e.g., smallest eigenvalue $\ge 1$). Without this, the "safety net" of the greedy algorithm's approximation ratio may vanish.
  • Operator Convexity: The authors note that operator convexity alone is insufficient to guarantee supermodularity, narrowing the class of applicable functions more than previously assumed.

Conclusion

By identifying the primitive of operator monotone functions as the key to supermodularity, this work provides a rigorous mathematical bridge between high-level spectral theory and practical greedy optimization. This allows researchers to confidently apply efficient algorithms to a wider array of problems in data subset selection and matrix approximation.

Summary updated

Abstract

We extend the multiplicative submodularity of the principal determinants of a nonnegative definite hermitian matrix to other spectral functions. We show that if $f$ is the primitive of a function that is operator monotone on an interval containing the spectrum of a hermitian matrix $A$, then the function $I\mapsto {\rm tr} f(A[I])$ is supermodular, meaning that ${\rm tr} f(A[I])+{\rm tr} f(A[J])\leq {\rm tr} f(A[I\cup J])+{\rm tr} f(A[I\cap J])$, where $A[I]$ denotes the $I\times I$ principal submatrix of $A$. We discuss extensions to self-adjoint operators on infinite dimensional Hilbert space and to $M$-matrices. We discuss an application to CUR approximation of nonnegative hermitian matrices.
BibTeX
@misc{friedland2010submodular,
  author = {Sergei Friedland and Stéphane Gaubert},
  title = {{Submodular spectral functions of principal submatrices of an hermitian matrix}},
  year = {2010},
  eprint = {1007.3478},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1007.3478},
}
Figure