A Caltech Library Service

Estimating operator norms using covering nets

Brandão, Fernando G. S. L. and Harrow, Aram W. (2015) Estimating operator norms using covering nets. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We present several polynomial- and quasipolynomial-time approximation schemes for a large class of generalized operator norms. Special cases include the 2→q norm of matrices for q>2, the support function of the set of separable quantum states, finding the least noisy output of entanglement-breaking quantum channels, and approximating the injective tensor norm for a map between two Banach spaces whose factorization norm through ℓ^n_1 is bounded. These reproduce and in some cases improve upon the performance of previous algorithms by Brandão-Christandl-Yard and followup work, which were based on the Sum-of-Squares hierarchy and whose analysis used techniques from quantum information such as the monogamy principle of entanglement. Our algorithms, by contrast, are based on brute force enumeration over carefully chosen covering nets. These have the advantage of using less memory, having much simpler proofs and giving new geometric insights into the problem. Net-based algorithms for similar problems were also presented by Shi-Wu and Barak-Kelner-Steurer, but in each case with a run-time that is exponential in the rank of some matrix. We achieve polynomial or quasipolynomial runtimes by using the much smaller nets that exist in ℓ_1 spaces. This principle has been used in learning theory, where it is known as Maurey's empirical method.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:We thank Jop Briet, Pablo Parrilo and Ben Recht for interesting discussions. FGSLB is supported by EPSRC. AWH was funded by NSF grants CCF-1111382 and CCF-1452616, ARO contract W911NF-12-1-0486 and a Leverhulme Trust Visiting Professorship VP2-2013-041. Part of this work was done while A.W. was visiting UCL.
Funding AgencyGrant Number
Engineering and Physical Sciences Research Council (EPSRC)UNSPECIFIED
Army Research Office (ARO)W911NF-12-1-0486
Leverhulme TrustVP2-2013-041
Record Number:CaltechAUTHORS:20160608-094748588
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67761
Deposited By: Tony Diaz
Deposited On:08 Jun 2016 17:00
Last Modified:03 Oct 2019 10:08

Repository Staff Only: item control page