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.
Matrix scaling @cite_28 is a well-studied special case of operator scaling. It has applications in numerical analysis, in approximating permanents @cite_9 and in combinatorial geometry @cite_19 . Very recently, much faster algorithms are developed for matrix scaling by two independent research groups @cite_18 @cite_15 . Cohen, Madry, Tsipras and Vladu @cite_18 obtain an algorithm for matrix scaling with running time @math , where @math is the number of nonzeros in the input matrix, @math is the ratio between the largest and the smallest entries in the optimal scaling solution, and @math is the error parameter of the output. Note that the algorithm is near linear time when @math is bounded by a polynomial in @math , but in general it could be exponentially large. Not much is known about upper bounding @math for specific instances, except when the input matrix is strictly positive @cite_31 . Our techniques for smoothed analysis in provides a new way to bound @math ; see Remark . In particular, this implies that the algorithm in @cite_18 is near linear time in a pseudorandom instance as defined in Definition (not necessarily strictly positive).
@cite_18 @cite_31 @cite_28 @cite_9 @cite_19 @cite_15
2605569246 2034025033 1990283121 2162960148 2543706324 2606394847
In this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We provide algorithms for both these problems that, ignoring logarithmic factors involving the dimension of the input matrix and the size of its entries, both run in time @math where @math is the amount of error we are willing to tolerate. Here, @math represents the ratio between the largest and the smallest entries of the optimal scalings. This implies that our algorithms run in nearly-linear time whenever @math is quasi-polynomial, which includes, in particular, the case of strictly positive matrices. We complement our results by providing a separate algorithm that uses an interior-point method and runs in time @math . In order to establish these results, we develop a new second-order optimization framework that enables us to treat both problems in a unified and principled manner. This framework identifies a certain generalization of linear system solving that we can use to efficiently minimize a broad class of functions, which we call second-order robust. We then show that in the context of the specific functions capturing matrix scaling and balancing, we can leverage and generalize the work on Laplacian system solving to make the algorithms obtained via this framework very efficient. An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy. We present a deterministic strongly polynomial algorithm that computes the permanent of a nonnegative n × n matrix to within a multiplicative factor of en. To this end we develop the first strongly polynomial-time algorithm for matrix scaling an important nonlinear optimization problem with many applications. Our work suggests a simple new (slow) polynomial time decision algorithm for bipartite perfect matching, conceptually different from classical approaches. ∗Hebrew University. Work supported in part by a grant of the Binational Israel-US Science Foundation. †Hebrew University ‡Hebrew University. Work partially supported by grant 032-7736 from the Israel Academy of Sciences. Part of this work was done during a visit to the Institute for Advanced Study, under the support of a Sloan Foundation grant 96-6-2. Design matrices are sparse matrices in which the supports of different columns intersect in a few positions. Such matrices come up naturally when studying problems involving point sets with many collinear triples. In this work we consider design matrices with block (or matrix) entries. Our main result is a lower bound on the rank of such matrices, extending the bounds proved in BDWY12,DSW12 for the scalar case. As a result we obtain several applications in combinatorial geometry. The first application involves extending the notion of structural rigidity (or graph rigidity) to the setting where we wish to bound the number of degrees of freedom' in perturbing a set of points under collinearity constraints (keeping some family of triples collinear). Other applications are an asymptotically tight Sylvester-Gallai type result for arrangements of subspaces (improving DH16 ) and a new incidence bound for high dimensional line curve arrangements. The main technical tool in the proof of the rank bound is an extension of the technique of matrix scaling to the setting of block matrices. We generalize the definition of doubly stochastic matrices to matrices with block entries and derive sufficient conditions for a doubly stochastic scaling to exist. We develop several efficient algorithms for the classical problem, which is used in many diverse areas, from preconditioning linear systems to approximation of the permanent. On an input @math matrix @math , this problem asks to find diagonal (scaling) matrices @math and @math (if they exist), so that @math @math -approximates a doubly stochastic, or more generally a matrix with prescribed row and column sums. We address the general scaling problem as well as some important special cases. In particular, if @math has @math nonzero entries, and if there exist @math and @math with polynomially large entries such that @math is doubly stochastic, then we can solve the problem in total complexity @math . This greatly improves on the best known previous results, which were either @math or @math . Our algorithms are based on tailor-made first and second order techniques, combined with other recent advances in continuous optimization, which may be of independent interest for solving similar problems.