It is known that random quantum channels exhibit significant violations of multiplicativity of maximum output p-norms for any p > 1. In this work, we show that a weaker variant of multiplicativity nevertheless holds for these channels. For any constant p > 1, given a random quantum channel ( N ) (i.e. a channel whose Stinespring representation corresponds to a random subspace S), we show that with high probability the maximum output p-norm of ( N ^ n ) decays exponentially with n. The proof is based on relaxing the maximum output ∞-norm of ( N ) to the operator norm of the partial transpose of the projector onto S, then calculating upper bounds on this quantity using ideas from random matrix theory.
As well as the final bound we obtain being of a similar order to that of Aubrun, the reader familiar with @cite_22 will notice that we need to prove some analogous combinatorial lemmas. However, it does not seem clear that the results given here could be obtained as a formal consequence of @cite_22 , or indeed vice versa; it would be interesting to determine whether this is the case. We also note two minor technical differences between this work and @cite_22 : Aubrun's result is only stated for @math (some recent work by Banica and Nechita removes this restriction @cite_5 ), and only for @math constant (so @math grows as a constant fraction of @math ). By contrast, here @math , @math and @math can be essentially arbitrary, although the bound we obtain becomes trivial if @math is too large as a fraction of @math .
@cite_5 @cite_22
2035588760 2081951537
Learning an unknown halfspace (also called a perceptron) from labeled examples is one of the classic problems in machine learning. In the noise-free case, when a halfspace consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that a halfspace consistent with a fraction @math of the examples exists (for some small constant @math ), it was not known how to efficiently find a halfspace that is correct on even 51 of the examples. Nor was a hardness result that ruled out getting agreement on more than 99.9 of the examples known. In this work, we close this gap in our understanding and prove that even a tiny amount of worst-case noise makes the problem of learning halfspaces intractable in a strong sense. Specifically, for arbitrary @math , we prove that given a set of examples-label pairs from the hypercube, a fraction @math of which can be explained by a halfspace, it is NP-hard to find a halfspace that correctly labels a fraction @math of the examples. The hardness result is tight since it is trivial to get agreement on @math the examples. In learning theory parlance, we prove that weak proper agnostic learning of halfspaces is hard. This settles a question that was raised by , in their work on learning halfspaces in the presence of random classification noise [Algorithmica, 22 (1998), pp. 35-52], and raised by authors of some more recent works as well. Along the way, we also obtain a strong hardness result for another basic computational problem: solving a linear system over the rationals. Hoeffding's U-statistics model combinatorial-type matrix parameters (appearing in CS theory) in a natural way. This paper proposes using these statistics for analyzing random compressed sensing matrices, in the non-asymptotic regime (relevant to practice). The aim is to address certain pessimisms of worst-case restricted isometry analyses, as observed by both Blanchard and Dossal, We show how U-statistics can obtain average-case analyses, by relating to statistical restricted isometry property (StRIP) type recovery guarantees. However unlike standard StRIP, random signal models are not required; the analysis used here holds in the almost sure (probabilistic) sense. For Gaussian bounded entry matrices, we show that both @math -minimization and LASSO essentially require on the order of @math measurements to respectively recover at least @math fraction, and @math fraction, of the signals. Noisy conditions are considered. Empirical evidence suggests our analysis to compare well to Donoho and Tanner's recent large deviation bounds for @math -equivalence, in the regime of block lengths @math with high undersampling ( @math measurements); similar system sizes are found in recent CS implementation. In this work, it is assumed throughout that matrix columns are independently sampled.