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.
As suggested by the smallest rank property, determinantal structures play an important role in our algorithm. This structure has been recently exploited in @cite_27 and @cite_22 for the fast computation of Gr "obner bases of zero-dimensional determinantal ideals and computing zero-dimensional critical loci of maps restricted to varieties in the generic case.
@cite_27 @cite_22
2949730746 2313549751 2036959865 1657130172
We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...). Critical points also play a central role in recent algorithms of effective real algebraic geometry. Experimentally, it has been observed that Gr "obner basis algorithms are efficient to compute such points. Therefore, recent software based on the so-called Critical Point Method are built on Gr "obner bases engines. Let @math be polynomials in @math of degree @math , @math be their complex variety and @math be the projection map @math . The critical points of the restriction of @math to @math are defined by the vanishing of @math and some maximal minors of the Jacobian matrix associated to @math . Such a system is algebraically structured: the ideal it generates is the sum of a determinantal ideal and the ideal generated by @math . We provide the first complexity estimates on the computation of Gr "obner bases of such systems defining critical points. We prove that under genericity assumptions on @math , the complexity is polynomial in the generic number of critical points, i.e. @math . More particularly, in the quadratic case D=2, the complexity of such a Gr "obner basis computation is polynomial in the number of variables @math and exponential in @math . We also give experimental evidence supporting these theoretical results. The determinantal complexity of a polynomial f is defined here as the minimal size of a matrix M with affine entries such that f = det M. This function gives a minoration of the more traditional size of an arithmetical formula. Consider the polynomial “permanent” perm d of a d × d matrix with entries X i,j . A conjecture in complexity theory says that the determinantal complexity (dc) of perm d should not be polynomial in d. In this article we prove that dc(permd)≥d2 2, improving the previously known minoration, 2d. We also begin a systematic study of the function dc, and compute it for the homogeneous polynomials of degree 2. We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation algorithms. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L1.We present some new observations concerning the relation of L1 to dimension, topology, and Euclidean distortion. We show that every n-point subset of L1 embeds into L2 with average distortion O(√log n), yielding the first evidence that the conjectured worst-case bound of O(√log n) is valid. We also address the issue of dimension reduction in Lp for p ∈ (1, 2). We resolve a question left open by M. Charikar and A. Sahai [Dimension reduction in the l1 norm, in: Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science, ACM, 2002, pp. 251-260] concerning the impossibility of dimension reduction with a linear map in the above cases, and we show that a natural variant of the recent example of Brinkman and Charikar [On the impossibility of dimension reduction in l1, in: Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, ACM, 2003, pp. 514-523], cannot be used to prove a lower bound for the non-linear case. This is acomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space. This paper establishes information-theoretic limits for estimating a finite-field low-rank matrix given random linear measurements of it. These linear measurements are obtained by taking inner products of the low-rank matrix with random sensing matrices. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp and the minimum-rank decoder is asymptotically optimal. The reliability function of this decoder is also derived by appealing to de Caen's lower bound on the probability of a union. The sufficient condition also holds when the sensing matrices are sparse-a scenario that may be amenable to efficient decoding. More precisely, it is shown that if the n × n-sensing matrices contain, on average, Ω(nlog n) entries, the number of measurements required is the same as that when the sensing matrices are dense and contain entries drawn uniformly at random from the field. Analogies are drawn between the aforementioned results and rank-metric codes in the coding theory literature. In fact, we are also strongly motivated by understanding when minimum rank distance decoding of random rank-metric codes succeeds. To this end, we derive minimum distance properties of equiprobable and sparse rank-metric codes. These distance properties provide a precise geometric interpretation of the fact that the sparse ensemble requires as few measurements as the dense one.