The Paulsen problem is a basic open problem in operator theory: Given vectors @math that are @math -nearly satisfying the Parseval's condition and the equal norm condition, is it close to a set of vectors @math that exactly satisfy the Parseval's condition and the equal norm condition? Given @math , the squared distance (to the set of exact solutions) is defined as @math where the infimum is over the set of exact solutions. Previous results show that the squared distance of any @math -nearly solution is at most @math and there are @math -nearly solutions with squared distance at least @math . The fundamental open question is whether the squared distance can be independent of the number of vectors @math . We answer this question affirmatively by proving that the squared distance of any @math -nearly solution is @math . Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any @math -nearly solution is @math . Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an @math -nearly solution is @math when @math is large enough and @math is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm.
The Brascamp-Lieb inequalities @cite_24 and their reversed form established by Barthe @cite_33 are general classes of inequalities with important applications in functional analysis and convex geometry (e.g. including Nelson's hypercontractivity inequality and the Brunn-Minkowski inequality as special cases). The optimal constants for thses inequalities are determined by Ball @cite_14 assuming the geometric condition (which is a condition similar to that in John's ellipsoid theorem). Garg, Gurvits, Oliveira and Wigderson @cite_12 show that the Brascamp-Lieb constants are equivalent to the capacity of an operator by a simple transformation, in which the geometric condition corresponds exactly to the doubly stochastic condition. Therefore, the algorithm in @cite_38 can be employed to scale the input to satisfying the geometric condition so as to compute the optimal constant. For our smoothed analysis in , we develop a new technique to proving a lower bound on the operator capacity and thus an upper bound on the Brascamp-Lieb constant. In particular, this implies improved bounds on the Brascamp-Lieb constants for perturbed instances in the rank-one case (which is the case that Brascamp and Lieb proved in @cite_24 ). See @cite_12 and the references therein for applications of these bounds to non-linear Brascamp-Lieb inequalities.
@cite_38 @cite_14 @cite_33 @cite_24 @cite_12
2606436810 2261415748 2037726123 1993000235 2950633396
In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over @math is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time (whether or not randomization is allowed). The algorithm efficiently solves the "word problem" for the free skew field, and the identity testing problem for arithmetic formulae with division over non-commuting variables, two problems which had only exponential-time algorithms prior to this work. The main contribution of this paper is a complexity analysis of an existing algorithm due to Gurvits, who proved it was polynomial time for certain classes of inputs. We prove it always runs in polynomial time. The main component of our analysis is a simple (given the necessary known tools) lower bound on central notion of capacity of operators (introduced by Gurvits). We extend the algorithm to actually approximate capacity to any accuracy in polynomial time, and use this analysis to give quantitative bounds on the continuity of capacity (the latter is used in a subsequent paper on Brascamp-Lieb inequalities). Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, approximation of the permanent and naturally in non-commutative algebra. We provide a detailed account of some of these sources and their interconnections. We prove a reverse form of the multidimensional Brascamp-Lieb inequality. Our method also gives a new way to derive the Brascamp-Lieb inequality and is rather convenient for the study of equality cases. The best possible constant Dmt in the inequality | ∬ dx dyf(x)g(x —y) h(y)| |, 1 p + llq+ 1 t = 2, is determined; the equality is reached if , g, and h are appropriate Gaussians. The same is shown to be true for the converse inequality (0 < p, q < 1, t < 0), in which case the inequality is reversed. Furthermore, an analogous property is proved for an integral of k functions over n variables, each function depending on a linear combination of the n variables; some of the functions may be taken to be fixed Gaussians. Two applications are given, one of which is a pr∞f of Nelson’s hypercontractive inequality. The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. While their structural theory is very well understood, far less is known about computing their main parameters. We give polynomial time algorithms to compute feasibility of BL-datum, the optimal BL-constant and a weak separation oracle for the BL-polytope. The same result holds for the so-called Reverse BL inequalities of Barthe. The best known algorithms for any of these tasks required at least exponential time. The algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by Gurvits, for which the present authors have provided a polynomial time algorithm. This reduction implies algorithmic versions of many of the known structural results, and in some cases provide proofs that are different or simpler than existing ones. Of particular interest is the fact that the operator scaling algorithm is continuous in its input. Thus as a simple corollary of our reduction we obtain explicit bounds on the magnitude and continuity of the BL-constant in terms of the BL-data. To the best of our knowledge no such bounds were known, as past arguments relied on compactness. The continuity of BL-constants is important for developing non-linear BL inequalities that have recently found so many applications.