21
$\begingroup$

While analyzing convergence speed of stochastic-gradient methods for convex optimization problems, Recht et al (2011) posed a tantalizing conjecture. It seems quite tricky, so after having struggled a bit with it, I decided to bring it to the attention of the MO community.

Among other questions, Recht and Re (RR) [1] pose the following Arithmetic-Mean, Geometric-Mean conjecture concerning symmetrized products:

RR. Let $A_1,\ldots,A_n$ be symmetric positive definite matrices. Let $\pi \in \mathfrak{S}_n$, where $\mathfrak{S}_n$ denotes the symmetric group. Let $P_{\pi} := \prod_{i=1}^n A_{\pi(i)}$. Then, $$\begin{equation*} \left\|\frac{1}{n!}\sum_{\pi \in \mathfrak{S}_n} P_{\pi}\right\| \le \left\|\left(\frac{1}{n}\sum_{i=1}^n A_i\right)^n\right\|, \end{equation*}$$ where $\|\cdot\|$ denotes the spectral norm.

Playing around a bit, it seems that in fact, the following much stronger conjecture should be true, but as of now, I don't know how to prove it---so I'm putting it out here. Hopefully, someone will be able to suggest to me potential areas of math where I could go to further educate myself about related inequalities.

(S., 2011). Let $\sigma(\cdot)$ denote the singular value map, i.e., the map that associates to a matrix the vector of its singular values (arranged in decreasing order). And let $\prec_w$ denote weak majorization. Then, $$\begin{equation*} \sigma^{1/n}\left(\frac{1}{n!}\sum_{\pi \in \mathfrak{S}_n} P_{\pi}\right) \prec_w \sigma\left(\frac{1}{n}\sum_{i=1}^n A_i\right). \end{equation*}$$


Notes.

(a) The two matrix version of the my conjecture follows immediately from a stronger conjecture of Bhatia and Kittaneh that was actually recently resolved in Ref. [2].

(b) It seems that for random matrices, Recht and Re proved their conjecture (because everything just disentangles easily); see cited paper for details.

REFERENCES

[1]. B. Recht and C. Re (2012). Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences.

[2]. S. W. Drury, On a question of Bhatia and Kittaneh, Linear Algebra and its Applications, 437 (2012) pp. 1955--1960.

$\endgroup$
  • $\begingroup$ Since you are summing over the $n$th symmetric group while you have a list of $m$, rather than $n$, matrices, could you make the highlighted inequalities clearer by writing explicitly what the range of summation is on the right side ($i$ runs from what to what)? $\endgroup$ – KConrad Apr 6 '13 at 12:59
  • $\begingroup$ @KConrad: thanks for catching that indexing typo. Now fixed. It is $n$ throughout. $\endgroup$ – Suvrit Apr 6 '13 at 16:55
  • 1
    $\begingroup$ What do you mean by "The two matrix version of the my conjecture follows immediately from a stronger conjecture of Bhatia and Kittaneh that was actually recently resolved"? $\endgroup$ – Betrand Apr 9 '13 at 14:12
  • 1
    $\begingroup$ @Betrand: In the two matrix case, the conjecture actually either follows directly, because it's just $\| |(AB+BA)/2|^{1/2} \| \le (1/2)\|A+B\|$ (for any unitarily invariant norm)... $\endgroup$ – Suvrit Apr 9 '13 at 14:57
  • 1
    $\begingroup$ @hänsel alas, if it were only that simple! (the linked article of Recht and Re shows a nice counterexample I think); also, proofs are known now for $n$ a multiple of 3, but the general case is still open. $\endgroup$ – Suvrit Sep 30 '18 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.