PaperlayerView exact revision on arXiv

Source-linked AI summary

Semidefinite approximations of the matrix logarithm

Hamza Fawzi, James Saunderson, Pablo A. Parrilo

arXiv:1705.00812v2math.OC

TL;DR

The logarithm cannot be exactly modeled by semidefinite optimization, although its operator concavity supports important matrix-function results. This paper constructs small semidefinite approximations that preserve operator concavity, extending them to related functions and perspectives. The approximations apply to optimization involving the logarithm and quantum relative entropy.

  • Problem

    Semidefinite feasible regions are semialgebraic, so they cannot exactly represent non-semialgebraic functions such as the logarithm.

    Source: §1 · p. 1

  • Method

    The paper constructs small semidefinite approximations of the logarithm that preserve operator concavity and extends the approach to related functions and perspectives.

    Source: §1 · p. 2, §1.1 · p. 4

  • Results

    The paper develops accurate, small semidefinite descriptions for the matrix logarithm and extends approximation strategies to operator-monotone and operator-concave functions.

    Source: §1 · p. 2

  • Takeaways & Limitations

    These approximations support semidefinite optimization involving the matrix logarithm and related functions, including quantum relative entropy.

    Source: §1 · p. 2

    The authors report no known efficiently computable self-concordant barrier for the operator relative entropy cone.

    Source: §6 · p. 20

Abstract

from arXiv · show

The matrix logarithm, when applied to Hermitian positive definite matrices, is concave with respect to the positive semidefinite order. This operator concavity property leads to numerous concavity and convexity results for other matrix functions, many of which are of importance in quantum information theory. In this paper we show how to approximate the matrix logarithm with functions that preserve operator concavity and can be described using the feasible regions of semidefinite optimization problems of fairly small size. Such approximations allow us to use off-the-shelf semidefinite optimization solvers for convex optimization problems involving the matrix logarithm and related functions, such as the quantum relative entropy. The basic ingredients of our approach apply, beyond the matrix logarithm, to functions that are operator concave and operator monotone. As such, we introduce strategies for constructing semidefinite approximations that we expect will be useful, more generally, for studying the approximation power of functions with small semidefinite representations.

1 Introduction

Because semidefinite feasible regions are semialgebraic, they cannot exactly model the logarithm; the paper develops small semidefinite approximations that preserve operator concavity. It extends the approach to related functions and perspectives, including applications to quantum relative entropy.

1 Introduction

  • Semidefinite feasible regions are semialgebraic, so they cannot exactly model the logarithm; the paper therefore studies accurate approximations with small semidefinite descriptions.The motivation is that semidefinite representations support optimization, while the logarithm is not exactly representable this way.Source: §1 · p. 1

1.1 Key ideas

  • Positive-weight quadrature of integral representations yields semidefinite-representable approximations that preserve concavity, including for the logarithm.For the logarithm, the integrand is operator concave and has a semidefinite representation.Source: §1.1 · p. 3
  • Successive square rooting improves the logarithm approximation while retaining concavity and semidefinite representability; related functional equations support extensions to other functions.The paper gives the logarithmic mean and Gauss’s arithmetic-geometric mean as examples of functions with suitable functional equations.Source: §1.1 · pp. 3–4
  • Homogenizing the approximations extends them to noncommutative perspectives, allowing scalar-log approximations to approximate operator relative entropy and quantum relative entropy.The noncommutative perspective is jointly concave when the underlying function is operator concave.Source: §1.1 · p. 4

1.2 Related work

  • Unlike earlier matrix-logarithm computations, the paper emphasizes that its Padé-based approximation preserves logarithmic concavity properties and can be modeled with semidefinite constraints.The cited numerical-analysis method uses successive square rooting with a diagonal Padé approximant.Source: §1.2 · pp. 4–5

2 Approximating logarithm

The section constructs concave, semidefinite-representable approximations of the logarithm using quadrature and successive square rooting. It establishes uniform approximation on a bounded interval and corresponding error guarantees for the relative entropy cone.

2 Approximating logarithm

  • Positive-weight Gaussian quadrature of the logarithm’s integral representation produces r_m, a concave semidefinite-representable rational approximation that is also its type-(m,m) Padé approximant.The Padé approximant matches the first 2m+1 Taylor coefficients of log.Source: §2 · p. 6
  • The approximation r_m,k first takes the 2^k-th root of x, approximating closer to 1, then applies r_m and scales back.This composition remains concave and semidefinite representable.Source: §2 · p. 7

Error bounds

  • For fixed a>1 and ϵ>0, a semidefinite-representable function approximates log within ϵ throughout [1/a, a].The theorem states that the representation size grows with improved approximation quality.Source: Error bounds · p. 7
  • The scalar relative-entropy-cone approximation uses the perspective of r_m,k and can be formulated with 2×2 linear matrix inequalities, hence second-order cone programming.The relative entropy cone is the epigraph of x log(x/y).Source: Error bounds · pp. 7–8
  • When a^-1y≤x≤ay, membership in either the relative entropy cone or its approximation implies membership in the other after increasing t by xϵ.The theorem gives both inclusion directions under this bounded-ratio condition.Source: Error bounds · p. 8

3 Operator concavity, noncommutative perspectives and the operator relative entropy cone

The section carries scalar logarithm approximations into the matrix setting while preserving operator concavity, then uses noncommutative perspectives to approximate operator and quantum relative entropy cones.

3.1 Operator concavity of logarithm and its approximation

  • The approximants rm and rm,k preserve operator concavity, and the matrix hypograph of rm has a semidefinite representation.The paper derives rm as a nonnegative combination of operator-concave ft functions and establishes operator concavity for rm,k.Source: §3.1 · p. 9

3.2 Approximating the operator relative entropy cone

  • Theorem 3 gives an explicit semidefinite description of the approximating operator relative entropy cone, with constraints parameterized by Gauss–Legendre quadrature nodes and weights.The nodes and weights are for m-point quadrature on [0, 1].Source: §3.2 · p. 10

3.3 Quantum relative entropy

  • A noncommutative-perspective representation expresses the quantum relative entropy epigraph constraint D(A∥B) ≤ τ through membership in the approximating operator relative entropy cone.The cone construction also yields semidefinite approximations of the quantum relative entropy constraint.Source: §3 · p. 8, §3.2 · p. 9, §3.3 · p. 11
  • A Schur-complement representation of the rational building block reduces the approximation’s block sizes for quantum relative entropy.The reduction replaces m + k blocks of size 2n^2 × 2n^2 with m blocks of size (n^2 + 1) × (n^2 + 1) and k blocks of size 2n^2 × 2n^2.Source: §3.3 · p. 12

4 Approximating operator concave functions

The section extends semidefinite approximation methods from the logarithm to cones built from perspectives of operator-concave functions. It uses integral representations and functional equations to obtain approximations with small semidefinite descriptions.

4.1 Approximations via L¨owner’s theorem

  • Operator-monotone functions can be approximated on [1/a, a] within ε by rational functions with semidefinite representation size O(log(1/ε)).The approximants are also operator monotone and operator concave, enabling approximation of matrix hypographs and noncommutative perspectives.Source: §4.1 · p. 13
  • Positive operator-monotone functions have perspectives monotone in both arguments, a property preserved by quadrature approximations.This follows from an alternative integral representation whose rational building blocks are monotone in both arguments.Source: §4.1 · pp. 13–14

4.2 Improved approximations via functional equations

  • Functional equations Pg ◦ Φ = Pg enable smaller semidefinite approximations when Φ has the required monotonicity and contraction properties.The arguments also extend to the matrix setting.Source: §4.2 · p. 14

4.2.1 Structure of approximations

  • When Φ is built from positive operator-monotone h1 and h2, the recursive approximants remain positive, jointly concave, and jointly monotone.If the cones for h1 and h2 have description sizes s1 and s2, the resulting size is 2m + k(s1 + s2).Source: §4.2.1 · p. 15

4.2.2 Approximation error

  • Functional-equation approximations require O(log(1/ε)) size under linear contraction and O(log log(1/ε)) under quadratic contraction.These bounds apply to positive operator-monotone functions satisfying the theorem’s assumptions.Source: §4.2.2 · p. 16
  • The theorem gives interval approximations for both the logarithmic mean and the arithmetic-geometric mean.The logarithmic-mean example concerns g(x) = (x − 1)/log(x); the arithmetic-geometric-mean example concerns g(x) = AGM(x, 1).Source: §4.2.2 · pp. 16–17
  • For operator-monotone functions that are not positive-valued, the construction needs modifications, including an affine second argument for Φ.The affine condition is required because the rational approximation is not generally monotone in its second argument.Source: §4.2.2 · p. 17

5 Numerical experiments

The experiments evaluate the approximation method on scalar entropy and geometric-programming problems, then test a matrix variational formula for trace. Comparisons use Mosek references where described, but the supplied passages do not report table cell values.

5 Numerical experiments

  • The scalar tests use Mosek’s dedicated maximum-entropy and geometric-programming routines as reference solvers, which do not handle matrix problems such as quantum relative entropy.The paper separately tests a matrix variational formula for trace.Source: §5 · p. 17, §5.3 · p. 18

5.1 Entropy problems

  • The method can be much faster than CVX successive approximation while achieving the same accuracy on maximum-entropy problems.The comparison uses random instances, with (m, k) = (3, 3); accuracy is measured against Mosek’s maximum-entropy solver.Source: §5.1 · p. 17, Table 2 · p. 18

5.3 Variational formula for trace

  • For matrix functions, the experiments compare the variational expression’s value with Tr[Y] on randomly generated positive definite matrices.The problems are implemented in CVX and solved using SDPT3; Table 4 reports |p − 1| for trace-one matrices.Source: §5.3 · p. 18, Table 4 · p. 19

5.2 Geometric programming

  • The geometric-programming experiments compare the method with CVX successive approximation on random instances, measuring absolute error against Mosek.The instances use five-term objectives and constraints, and the method uses (m, k) = (3, 3).Source: §5.2 · p. 18, Table 3 · p. 19

6 Discussion

The discussion identifies open questions about the size and approximation power of semidefinite representations, alongside extensions to other function families and free LMI representations. It also notes that an efficiently computable self-concordant barrier for the operator relative entropy cone is not known.

Lower bounds

  • The paper leaves open whether its logarithm approximation size is optimal and calls for lower bounds on the required second-order cone size.It also asks which properties determine how difficult a concave function is to approximate by second-order cone programs.Source: §6 · pp. 19–20

Smaller semidefinite approximations for quantum relative entropy

  • The discussion asks whether quantum relative entropy can be approximated with LMIs of size O(n), rather than the constructed size O(n^2).The desired approximations would have similar quality.Source: §6 · p. 20

Self-concordant barriers for the operator relative entropy cone

  • No efficiently computable self-concordant barrier is known for the operator relative entropy cone.Such a barrier could support direct interior-point optimization as an alternative to semidefinite approximation.Source: §6 · p. 20

Approximating other families of convex functions via quadrature

  • Integral representations with simple semidefinite representations for their kernels can support quadrature-based approximations beyond operator-monotone functions, including Stieltjes and certain hypergeometric functions.The paper suggests these representations may help study approximate extension complexity.Source: §6 · p. 20

Free semidefinite representation

  • The paper’s free LMI representation of the hypograph of f_t also represents its noncommutative perspective, and the authors ask which operator-concave functions admit free LMI representations.The passage states this perspective result for operator-concave functions with a free LMI representation.Source: §6 · p. 20

A Background on approximation theory

The appendix reviews Gaussian quadrature and Padé approximants, then relates quadrature applied to an integral representation of an operator-monotone function to its Padé approximant at 1. It also states that error bounds are derived for this rational approximation.

A Background on approximation theory

  • Gaussian quadrature chooses nodes and positive weights so that all polynomials through degree 2m − 1 are integrated exactly.For the uniform measure on [−1, 1], this is Gauss-Legendre quadrature.Source: A Background on approximation theory · p. 21
  • A Padé approximant is a rational function whose Taylor expansion matches as many coefficients of the target function at a point as possible, subject to its numerator and denominator degrees.The appendix specifies at least the first m + n + 1 coefficients for an (m, n)-approximant.Source: A Background on approximation theory · p. 21

B Properties and error bounds of Gaussian quadrature-based approximations

  • For functions with the stated integral representation, Gaussian quadrature produces a rational approximation that coincides with the Padé approximant at x = 1.The appendix also derives error bounds; it identifies these integral representations with operator-monotone functions.Source: B Properties and error bounds of… · p. 21

B.1 Connection with Pad´e approximant

For functions with the stated integral form, the rational approximation obtained by Gaussian quadrature is the diagonal Padé approximant at x = 1. The proof uses moment matching to establish agreement of Taylor coefficients.

B.1 Connection with Padé approximant

  • Gaussian quadrature yields the (m, m) Padé approximant at x = 1 for functions of the stated integral form.Its moment matching makes the rational function agree with the first 2m Taylor coefficients, and its numerator and denominator each have degree m.Source: §B.1 · p. 22

B.2 Error bounds

The approximation error is analyzed using standard methods and is essentially controlled by the decay of the integrand’s Chebyshev coefficients. For the rational functions considered, those coefficients can be computed exactly.

B.2 Error bounds

  • The error analysis uses standard methods to bound the quality of the approximation.The passage points to Tre13 as an example.Source: §B.2 · p. 22
  • Approximation error is essentially controlled by the decay of the integrand’s Chebyshev coefficients.Source: §B.2 · p. 22
  • For the rational functions considered, the Chebyshev coefficients can be computed exactly.Source: §B.2 · p. 22

B.2.1 Quadrature error bounds for operator monotone functions

This section bounds Gaussian-quadrature approximations using Chebyshev expansions and derives sign comparisons between the approximation and the target function. It also states that similar bounds apply to a related positive operator-monotone function.

B.2.1 Quadrature error bounds for operator monotone functions

  • The error analysis uses Chebyshev coefficients, which can be computed exactly for the rational integrands under consideration.The integrals are transformed from [0, 1] to [−1, 1] to use standard arguments.Source: §B.2.1 · p. 22
  • For m≥1 and x>0, Proposition 6 gives an error bound for the Gaussian-quadrature rational approximation of a function with the stated integral representation.Source: §B.2.1 · p. 23
  • When ν is invariant under t↦1−t, the error bound can be improved; invariance under t↦−t also makes the quadrature measure symmetric, leaving only even Chebyshev coefficients in the error bound.Source: §B.2.1 · pp. 23–24
  • The quadrature error has a derivative-based expression that yields r_m(x)≥g(x) for 0<x≤1 and r_m(x)≤g(x) for x≥1.At x=1, the passage states g(x)=r_m(x).Source: §B.2.1 · pp. 23–24
  • Similar error bounds are stated for the related rational approximation r⁺_m of a positive operator-monotone function.Source: §B.2.1 · p. 24

B.2.2 The special case of log: proofs of Proposition 1 and Theorem 1

For the logarithm, the representing measure is uniform and invariant under t↦1−t, so Proposition 6 applies. The proof then scales the approximation error and selects parameters for a bounded interval.

B.2.2 The special case of log: proofs of Proposition 1 and Theorem 1

  • The logarithm’s uniform representing measure is invariant under t↦1−t, allowing Proposition 6 to be applied.Source: §B.2.2 · p. 24
  • The error for the scaled logarithm approximation is obtained by evaluating at x^(1/2^k) and scaling the error by 2^k.Source: §B.2.2 · p. 24
  • The proof’s asymptotic analysis uses sinh²(2x)tanh^(2m−1)(x)=4x^(2m+1)+O(x^(2m+3)).Source: §B.2.2 · p. 25
  • For x in [1/a,a], the proof chooses k₁ = ⌈log₂ logₑ(a)⌉ + 1, and by that choice uses 2k₁−1 ≤ logₑ(a) in its bound.Source: §B.2.2 · p. 25

B.2.3 Proof of Theorem 7

Theorem 7’s proof bounds approximation error under a linear contraction condition and controls the growth of iterated inputs. The following section characterizes the building-block function and its perspective semidefinitely.

B.2.3 Proof of Theorem 7

  • Under the linear contraction property, the error bound decays as O(c^(−km)) when m is chosen approximately proportional to k.The proof identifies log(x_k/y_k) and √(x_k y_k) as the terms to control.Source: §B.2.3 · p. 25
  • For inputs with a−1≤x/y≤a, the iterates satisfy a bound on x_k+y_k obtained from the concavity of h₁ and h₂.The proof derives x_k+y_k≤b^k(x+y).Source: §B.2.3 · p. 26
  • The approximation r=r_m,k has a semidefinite representation of size O(m+k), treating the sizes for h₁ and h₂ as constant.Source: §B.2.3 · p. 26

C Semidefinite description of ft

D Integral representations of operator monotone functions

This section derives integral representations for operator-monotone functions by reworking a theorem on operator-monotone functions on (−1, 1). A change of coordinates yields a probability measure on [0, 1], with an additional representation in the positive-valued case.

D Integral representations of operator monotone functions

Loading 1705.00812v2…