Let @math be a linear matrix, or pencil, generated by given symmetric matrices @math of size @math with rational entries. The set of real vectors x such that the pencil is positive semidefinite is a convex semi-algebraic set called spectrahedron, described by a linear matrix inequality (LMI). We design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree @math of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semidefinite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear B 'ezout bound of @math . When @math (resp. @math ) is fixed, such a bound, and hence the complexity, is polynomial in @math (resp. @math ). We conclude by providing results of experiments showing practical improvements with respect to state-of-the-art computer algebra algorithms.
Also, in @cite_49 , a version of @cite_40 dedicated to spectrahedra exploiting some of their structural properties, decides whether a linear matrix inequality @math has a rational solution, that is whether @math contains a point with coordinates in @math . Remark that such an algorithm is not sufficient to solve our problem, since, in some degenerate but interesting cases, @math is not empty but does not contain rational points: in Section we will illustrate the application of our algorithm to one of these examples.
@cite_40 @cite_49
2011936157 2950958145 2034070643 1859301526
Consider a (D x D) symmetric matrix A whose entries are linear forms in Q[X1, ..., Xk] with coefficients of bit size ≤ τ. We provide an algorithm which decides the existence of rational solutions to the linear matrix inequality A ≥ 0 and outputs such a rational solution if it exists. This problem is of first importance: it can be used to compute algebraic certificates of positivity for multivariate polynomials. Our algorithm runs within (k≤)O(1)2O(min(k, D)D2)DO(D2) bit operations; the bit size of the output solution is dominated by τO(1)2O( (k, D)D2). These results are obtained by designing algorithmic variants of constructions introduced by Klep and Schweighofer. This leads to the best complexity bounds for deciding the existence of sums of squares with rational coefficients of a given polynomial. We have implemented the algorithm; it has been able to tackle Scheiderer's example of a multivariate polynomial that is a sum of squares over the reals but not over the rationals; providing the first computer validation of this counter-example to Sturmfels' conjecture. We consider the problem of selecting the best subset of exactly @math columns from an @math matrix @math . We present and analyze a novel two-stage algorithm that runs in @math time and returns as output an @math matrix @math consisting of exactly @math columns of @math . In the first (randomized) stage, the algorithm randomly selects @math columns according to a judiciously-chosen probability distribution that depends on information in the top- @math right singular subspace of @math . In the second (deterministic) stage, the algorithm applies a deterministic column-selection procedure to select and return exactly @math columns from the set of columns selected in the first stage. Let @math be the @math matrix containing those @math columns, let @math denote the projection matrix onto the span of those columns, and let @math denote the best rank- @math approximation to the matrix @math . Then, we prove that, with probability at least 0.8, @math This Frobenius norm bound is only a factor of @math worse than the best previously existing existential result and is roughly @math better than the best previous algorithmic result for the Frobenius norm version of this Column Subset Selection Problem (CSSP). We also prove that, with probability at least 0.8, @math This spectral norm bound is not directly comparable to the best previously existing bounds for the spectral norm version of this CSSP. Our bound depends on @math , whereas previous results depend on @math ; if these two quantities are comparable, then our bound is asymptotically worse by a @math factor. We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace. Given a large data matrix @math , we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution @math , or instead @math contains a principal submatrix @math whose entries have marginal distribution @math . As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided @math for a suitable constant @math . However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when @math . Recently Meka and Wigderson meka2013association , proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree- @math SOS relaxation, and study the construction of meka2013association to prove that SOS fails unless @math . An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erd "os-Renyi random graph.