Restricted Isometry Property of Matrices with?Independent Columns and Neighborly Polytopes by?Random Sampling

This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors ±X ₁,…,±X _N ∈ℝ ⁿ , (N≥n). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a subexponential tail inequality possess the restricted isometry property with overwhelming probability. We show that such “sensing” matrices are valid for the exact reconstruction process of m-sparse vectors via ℓ ₁ minimization with m≤Cn/log ²(cN/n). The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if K⊂ℝ ⁿ is a convex body and X ₁,…,X _N ∈K are i.i.d. random vectors uniformly distributed on K, then, with overwhelming probability, the symmetric convex hull of these points is an m-centrally-neighborly polytope with m∼n/log ²(cN/n).     

On conditionally positive definite dot product kernels

Let m and n be fixed, positive integers and P a space composed of real polynomials in m variables. The authors study functions f ： R →R which map Gram matrices, based upon n points of R^m, into matrices, which are nonnegative definite with respect to P Among other things, the authors discuss continuity, differentiability, convexity, and convexity in the sense of Jensen, of such functions     

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

Rearrangements of (0–1) matrices

Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn ²−m zeros, 0<m<n ². The problem of finding the maximum ofs(A ²) over this set, wheres(A ²) is the sum of the entries ofA ²,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n ² −k ² andm=k ²,k ²>(n ²/2). This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation of this paper.     

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

We study random subgraphs of the n-cube {0,1}ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p−p_c(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2^−n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log 2)nε⁻², and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for the size of the largest component is at least Θ(ε2ⁿ), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,” and relies heavily on the specific geometry of the n-cube.     

Generalizations of the odd degree theorem and applications

LetV ⊂ ℙℝ ⁿ be an algebraic variety, such that its complexificationV _ℂ ⊂ ℙ ⁿ is irreducible of codimensionm ≥ 1. We use a sufficient condition on a linear spaceL ⊂ ℙℝ ⁿ of dimensionm + 2r to have a nonempty intersection withV, to show that any six dimensional subspace of 5 × 5 real symmetric matrices contains a nonzero matrix of rank at most 3.     

On quartic half-arc-transitive metacirculants

Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1, n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ ^m has at least one fixed vertex. A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In this article quartic half-arc-transitive metacirculants are explored and their connection to the so called tightly attached quartic half-arc-transitive graphs is explored. It is shown that there are three essentially different possibilities for a quartic half-arc-transitive metacirculant which is not tightly attached to exist. These graphs are extensively studied and some infinite families of such graphs are constructed. Both authors were supported in part by “ARRS – Agencija za znanost Republike Slovenije”, program no. P1-0285.     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.     

Computing Vertex Connectivity: New Bounds from Old Techniques

The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ³ + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ₁nmlog(n²/m)) where κ₁ ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n²/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.     

Convex integration with constraints and applications to phase transitions and partial differential equations

We study solutions of first order partial differential relations Du∈K, where u:Ω⊂ℝ ⁿ →ℝ ^m is a Lipschitz map and K is a bounded set in m×n matrices, and extend Gromov’s theory of convex integration in two ways. First, we allow for additional constraints on the minors of Du and second we replace Gromov’s P-convex hull by the (functional) rank-one convex hull. The latter can be much larger than the former and this has important consequences for the existence of ‘wild’ solutions to elliptic systems. Our work was originally motivated by questions in the analysis of crystal microstructure and we establish the existence of a wide class of solutions to the two-well problem in the theory of martensite. Received April 23, 1999 / final version received September 11, 1999     

The generic division rings

LetA=k (X ₁, X₂..., X_m) be the division ring generated by genericn×n matrices over a fieldk; thenA is not a crossed product in the following cases: (i) there exists a primeq such thatq ³ℛn;(ii)[k:Q]=m, whereQ is the field of rationals, then if eitherq ³ℛn for someq for whichq-1ℛm, orq ²/nn for some other prime; (iii)k=Z _p ^r a finite field ofp ^r elements and eitherq ³ℛn for sameqℛp ^r-1 orq ²ℛn for some other primes. Other cases are also considered.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

l p n Superspaces of spans of independent random variables

We show that for 1 ≦p < ∞,p ≠ 2, ifɛ > 0 is small enough andX ≦L _p is the span ofn independent Rademacher functions orn independent Gaussian random variables, then any superspaceY ofX satisfyingd(Y,L _p ^m ) ≦ 1 +ɛ has dimension larger thanr ⁿ, wherer =r(ɛ, p) > 1. This forms part of the author’s doctoral dissertation prepared at Texas A&M University under the direction of Professor W. B. Johnson. Supported in part by NSF DMS-85 00764.     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000     

On Intersection Problem for Perfect Binary Codes

The main result is that to any even integer q in the interval 0 ≤ q ≤ 2^{n+1-2log(n+1)}, there are two perfect codes C₁ and C₂ of length n = 2^m − 1, m ≥ 4, such that |C₁ ∩ C₂| = q.     

Properties of <Emphasis Type="Italic">C</Emphasis><Superscript>1</Superscript>-smooth mappings with one-dimensional gradient range

We find necessary and sufficient conditions for a curve in ℝ ^m×n to be the gradient range of a C ¹-smooth function υ: Ω ⊂ ℝ ⁿ → ℝ ^m . We show that this curve has tangents in a weak sense; these tangents are rank 1 matrices and their directions constitute a function of bounded variation. We prove also that in this case v satisfies an analog of Sard’s theorem, while the level sets of the gradient mapping ▿υ: Ω → ℝ ^m×n are hyperplanes.     

On graded quotient modules of mapping class groups of surfaces

Let Γ _{g, n} be the mapping class group of a compact Riemann surface of genusg withn points preserved (2−2g−n<0,g≥1,n≥0). The Torelli subgroup of Γ _{g, n} has a natural weight filtration {Γ_{g, n}(m)} _m≥1. Each graded quotient gr ^m Γ _{g, n} ⊗ ℚ (m≥1) is a finite dimensional vector space over ℚ on which the group Sp(2g, ℚ)×S _n naturally acts. In this paper, we have determined the Sp(2g, ℚ)×S _n module structure of gr ^m Γ _{g, n} ⊗ ℚ for 1≤m≤3. This includes a verification of an expectation by S. Morita. Also, for generalm, we have identified a certain Sp(2g, ℚ)-irreducible component of gr ^m Γ _{g, n} ⊗ ℚ by constructing explicitly elements in these modules.     

Global stabilization of nonlinear systems by quadratic Lyapunov functions

The system x = A (t, x)x + B(t, x)u, where A(t, x) and B(t, x) are, respectively, n × n and n × m (m<n) continuous matrices whose elements are uniformly bounded for t ≽ t ₀ and x ∈ ℝ ⁿ , is considered. It is assumed that the system has relative degree q = n - m + 1, and the determinant of the matrix composed of the last m rows of the matrix B(t, x) is bounded away from zero for t ≽ t ₀ and x ∈ ℝ ⁿ . A special quadratic Lyapunov function with constant positive definite coefficient matrix H depending only on the range of variation of the coefficients in the matrices A(t, x) and B(t, x) is constructed and applied to obtain a control u(t, x) =7n ~B⋆ (t, x)H depending on a scalar parameter 7n under which the system is globally asymptotically stable provided that it is closed. Here, ~B (t, x) is the scalar matrix obtained from the matrix B(t, x) by setting the first n - m rows to zero.