Noncommutative am gm inequality proven true under size condition
When the noncommutative AM-GM inequality holds
Machine Learning
Summary
The researchers worked on a mathematical inequality that is usually true for ordinary numbers but can fail for more complex objects like matrices, where multiplication doesn't always work the same way forwards and backwards. They found a specific condition involving the size of these objects that guarantees the inequality still holds. To prove this, they used special mathematical techniques involving nodes on shapes called Boolean cubes and transformed the problem into a question about approximating integrals. Their work builds on previous examples that showed this inequality sometimes fails.
What this means in practice
- •For quantum information engineers: Confirm conditions when noncommutative inequalities hold, aiding analysis of quantum states and operations.
- •For numerical linear algebra developers: Use new bounds to improve algorithms that depend on matrix inequalities involving noncommuting matrices.
A theory result. No direct application yet.
Authors
Yimin Zhong
Abstract
In this note, we prove that the noncommutative AM-GM inequality holds if $n\ge 2\lceil m/2 \rceil^2$. The motivation comes from counterexamples constructed in [De Sa, Random reshuffling is not always better, NeurIPS2020]. The proof constructs a vertex measure based on the Chebyshev nodes on the Boolean cube to extract the distinct indices. The main difficulty is that the measure is not positive on non-integer nodes. The key technique comes from [Grigoriev, Complexity of Positivstellensatz proofs for the knapsack, Computational Complexity (2001)] and eventually transforms the problem into a quadrature estimate.