Search

We give a new deterministic construction of integer sensing matrices that can be used for the recovery of integer-valued signals in compressed sensing. This is a family of n × d integer matrices, d ≥ n , with bounded sup-norm and the property that no ℓ column vectors are linearly dependent, ℓ ≤ n . Further, if ℓ ≤ o (log n) then d / n → ∞ as n → ∞ . Our construction comes from particular sets of difference vectors of point-sets in R n that cannot be covered by few parallel hyperplanes. We construct examples of such sets on the 0 , ± 1 grid and use them for the matrix construction. We also show a connection of our constructions to a simple version of the Tarski's plank problem. [ABSTRACT FROM AUTHOR]

Let L be a full-rank lattice in ℝd and write L+ for the semigroup of all vectors with nonnegative coordinates in L. We call a basis X for L positive if it is contained in L+. There are infinitely many such bases, and each of them spans a conical semigroup S(X) consisting of all nonnegative integer linear combinations of the vectors of X. Such S(X) is a sub-semigroup of L+, and we investigate the distribution of the gaps of S(X) in L+, i.e. the points in L+ ∖ S(X). We describe some basic properties and counting estimates for these gaps. Our main focus is on the restrictive successive minima of L+ and of L+ ∖ S(X), for which we produce bounds in the spirit of Minkowski's successive minima theorem and its recent generalizations. We apply these results to obtain analogous bounds for the successive minima with respect to Weil heights of totally positive sub-semigroups of ideals in totally real number fields. [ABSTRACT FROM AUTHOR]

Given a primitive collection of vectors in the integer lattice, we count the number of ways it can be extended to a basis by vectors with sup-norm bounded by T, producing an asymptotic estimate as T \to \infty. This problem can be interpreted in terms of unimodular matrices, as well as a representation problem for a class of multilinear forms. In the 2-dimensional case, this problem is also connected to the distribution of Farey fractions. As an auxiliary lemma we prove a counting estimate for the number of integer lattice points of bounded sup-norm in a hyperplane in \mathbb R^n. Our main result on counting basis extensions also generalizes to arbitrary lattices in \mathbb R^n. Finally, we establish some basic properties of sparse representations of integers by multilinear forms. [ABSTRACT FROM AUTHOR]

This note supplies additions to our paper quoted in the title on integral spans of tight frames in Euclidean spaces. In that previous paper, we considered the case of an equiangular tight frame (ETF), proving that if its integral span is a lattice then the frame must be rational, but overlooking a simple argument in the reverse direction. Thus our first result here is that the integral span of an ETF is a lattice if and only if the frame is rational. Further, we discuss conditions under which such lattices are eutactic and perfect and, consequently, are local maxima of the packing density function in the dimension of their span. In particular, the unit ( 276 , 23 ) equiangular tight frame is shown to be eutactic and perfect. More general tight frames and their norm-forms are considered as well, and definitive results are obtained in dimensions two and three. [ABSTRACT FROM AUTHOR]

Let F (x) be a homogeneous polynomial in n ≥ 1 variables of degree 1 ≤ d ≤ n with integer coefficients so that its degree in every variable is equal to 1. We give some sufficient conditions on F to ensure that for every integer b there exists an integer vector a such that F (a) = b . The conditions provided also guarantee that the vector a can be found in a finite number of steps. [ABSTRACT FROM AUTHOR]