Physical Sciences and Mathematics Commons^™

A Sampling Kaczmarz-Motzkin Algorithm For Linear Feasibility, Jesus A. De Loera, Jamie Haddock, Deanna Needell

CMC Faculty Publications and Research

We combine two iterative algorithms for solving large-scale systems of linear inequalities, the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz method. We obtain a family of algorithms that generalize and extend both projection-based techniques. We prove several convergence results, and our computational experiments show our algorithms often outperform the original methods.

Biquasiles And Dual Graph Diagrams, Deanna Needell, Sam Nelson

CMC Faculty Publications and Research

We introduce dual graph diagrams representing oriented knots and links. We use these combinatorial structures to define corresponding algebraic structures we call biquasiles whose axioms are motivated by dual graph Reidemeister moves, generalizing the Dehn presentation of the knot group analogously to the way quandles and biquandles generalize the Wirtinger presentation. We use these structures to define invariants of oriented knots and links. In particular, we identify an example of a finite biquasile whose counting invariant distinguishes the chiral knot 9-32 from its mirror image, demonstrating that biquasile counting invariants are distinct from biquandle counting invariants.

Batched Stochastic Gradient Descent With Weighted Sampling, Deanna Needell, Rachel Ward

CMC Faculty Publications and Research

We analyze a batched variant of Stochastic Gradient Descent (SGD) with weighted sampling distribution for smooth and non-smooth objective functions. We show that by distributing the batches computationally, a significant speedup in the convergence rate is provably possible compared to either batched sampling or weighted sampling alone. We propose several computationally efficient schemes to approximate the optimal weights, and compute proposed sampling distributions explicitly for the least squares and hinge loss problems. We show both analytically and experimentally that substantial gains can be obtained

Tolerant Compressed Sensing With Partially Coherent Sensing Matrices, Tobias Birnbaum, Yonina C. Eldar, Deanna Needell

CMC Faculty Publications and Research

We consider compressed sensing (CS) using partially coherent sensing matrices. Most of CS theory to date is focused on incoherent sensing, that is, columns from the sensing matrix are highly uncorrelated. However, sensing systems with naturally occurring correlations arise in many applications, such as signal detection, motion detection and radar. Moreover, in these applications it is often not necessary to know the support of the signal exactly, but instead small errors in the support and signal are tolerable. In this paper, we focus on d-tolerant recovery, in which support set reconstructions are considered accurate when their locations match the true …

A Practical Study Of Longitudinal Reference Based Compressed Sensing For Mri, Samuel Birns, Bohyun Kim, Stephanie Ku, Kevin Stangl, Deanna Needell

CMC Faculty Publications and Research

Compressed sensing (CS) is a new signal acquisition paradigm that enables the reconstruction of signals and images from a low number of samples. A particularly exciting application of CS is Magnetic Resonance Imaging (MRI), where CS significantly speeds up scan time by requiring far fewer measurements than standard MRI techniques. Such a reduction in sampling time leads to less power consumption, less need for patient sedation, and more accurate images. This accuracy increase is especially pronounced in pediatric MRI where patients have trouble being still for long scan periods. Although such gains are already significant, even further improvements can be …

One-Bit Compressive Sensing Of Dictionary-Sparse Signals, Richard Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, Mary Wootters

CMC Faculty Publications and Research

One-bit compressive sensing has extended the scope of sparse recovery by showing that sparse signals can be accurately reconstructed even when their linear measurements are subject to the extreme quantization scenario of binary samples—only the sign of each linear measurement is maintained. Existing results in one-bit compressive sensing rely on the assumption that the signals of interest are sparse in some fixed orthonormal basis. However, in most practical applications, signals are sparse with respect to an overcomplete dictionary, rather than a basis. There has already been a surge of activity to obtain recovery guarantees under such a generalized sparsity model …

Optimizing Quantization For Lasso Recovery, Xiaoyi Gu, Shenyinying Tu, Hao-Jun Michael Shi, Mindy Case, Deanna Needell, Yaniv Plan

CMC Faculty Publications and Research

This letter is focused on quantized Compressed Sensing, assuming that Lasso is used for signal estimation. Leveraging recent work, we provide a framework to optimize the quantization function and show that the recovered signal converges to the actual signal at a quadratic rate as a function of the quantization level. We show that when the number of observations is high, this method of quantization gives a significantly better recovery rate than standard Lloyd-Max quantization. We support our theoretical analysis with numerical simulations.

Bernstein’S Lethargy Theorem In Fréchet Spaces, Asuman Güven Aksoy, Grzegorz Lewicki

CMC Faculty Publications and Research

In this paper we consider Bernstein’s Lethargy Theorem (BLT) in the context of Fréchet spaces. Let X be an infinite-dimensional Fréchet space and let V = {V_n} be a nested sequence of subspaces of X such that V_n ⊆ V_n+1 for any n ∈ N and X = S∞ _n=1 V_n. Let e_n be a decreasing sequence of positive numbers tending to 0. Under an additional natural condition on sup{dist(x, V_n)}, we prove that there exists x ∈ X and no ∈ N such that

e_n/3 ≤ dist(x, V …

Constrained Adaptive Sensing, Mark A. Davenport, Andrew K. Massimino, Deanna Needell, Tina Woolf

CMC Faculty Publications and Research

Suppose that we wish to estimate a vector x∈Cn from a small number of noisy linear measurements of the form y=Ax+z, where z represents measurement noise. When the vector x is sparse, meaning that it has only s nonzeros with s≪n, one can obtain a significantly more accurate estimate of x by adaptively selecting the rows of A based on the previous measurements provided that the signal-to-noise ratio (SNR) is sufficiently large. In this paper we consider the case where we wish to realize the potential of adaptivity but where the rows of A are subject to physical constraints. In …

On Arithmetic Lattices In The Plane, Lenny Fukshansky, Pavel Guerzhoy, Florian Luca

CMC Faculty Publications and Research

We investigate similarity classes of arithmetic lattices in the plane. We introduce a natural height function on the set of such similarity classes, and give asymptotic estimates on the number of all arithmetic similarity classes, semi-stable arithmetic similarity classes, and well-rounded arithmetic similarity classes of bounded height as the bound tends to infinity. We also briefly discuss some properties of the j-invariant corresponding to similarity classes of planar lattices.

Lattice Theory And Toeplitz Determinants, Albrecht Böttcher, Lenny Fukshansky, Stephan Ramon Garcia, Hiren Maharaj

CMC Faculty Publications and Research

This is a survey of our recent joint investigations of lattices that are generated by finite Abelian groups. In the case of cyclic groups, the volume of a fundamental domain of such a lattice is a perturbed Toeplitz determinant with a simple Fisher-Hartwig symbol. For general groups, the situation is more complicated, but it can still be tackled by pure matrix theory. Our main result on the lattices under consideration states that they always have a basis of minimal vectors, while our results in the other direction concern exact and asymptotic formulas for perturbed Toeplitz determinants. The survey is a …

Methods For Quantized Compressed Sensing, Hao-Jun Michael Shi, Mindy Case, Xiaoyi Gu, Shenyinying Tu, Deanna Needell

CMC Faculty Publications and Research

In this paper, we compare and catalog the performance of various greedy quantized compressed sensing algorithms that reconstruct sparse signals from quantized compressed measurements. We also introduce two new greedy approaches for reconstruction: Quantized Compressed Sampling Matching Pursuit (QCoSaMP) and Adaptive Outlier Pursuit for Quantized Iterative Hard Thresholding (AOP-QIHT). We compare the performance of greedy quantized compressed sensing algorithms for a given bit-depth, sparsity, and noise level.

Lattices From Tight Equiangular Frames, Albrecht Böttcher, Lenny Fukshansky, Stephan Ramon Garcia, Hiren Maharaj, Deanna Needell

CMC Faculty Publications and Research

We consider the set of all linear combinations with integer coefficients of the vectors of a unit tight equiangular (k,n) frame and are interested in the question whether this set is a lattice, that is, a discrete additive subgroup of the k-dimensional Euclidean space. We show that this is not the case if the cosine of the angle of the frame is irrational. We also prove that the set is a lattice for n=k+1 and that there are infinitely many k such that a lattice emerges for n=2k. We dispose of all cases in dimensions k at most 9. In …

Totally Isotropic Subspaces Of Small Height In Quadratic Spaces, Wai Kiu Chan, Lenny Fukshansky, Glenn Henshaw

CMC Faculty Publications and Research

Let K be a global field or Q, F a nonzero quadratic form on KN , N ≥ 2, and V a subspace of KN . We prove the existence of an infinite collection of finite families of small-height maximal totally isotropic subspaces of (V, F) such that each such family spans V as a K-vector space. This result generalizes and extends a well known theorem of J. Vaaler [16] and further contributes to the effective study of quadratic forms via height in the general spirit of Cassels’ theorem on small zeros of quadratic forms. All bounds on height are …

On An Effective Variation Of Kronecker's Approximation Theorem, Lenny Fukshansky

CMC Faculty Publications and Research

Let Λ ⊂ Rn be an algebraic lattice, coming from a projective module over the ring of integers of a number field K. Let Z ⊂ Rn be the zero locus of a finite collection of polynomials such that Λ |⊂ Z or a finite union of proper full-rank sublattices of Λ. Let K1 be the number field generated over K by coordinates of vectors in Λ, and let L1, . . . , Lt be linear forms in n variables with algebraic coefficients satisfying an appropriate linear independence condition over K1. For each ε > 0 and a ∈ Rn, …

A Note On Practical Approximate Projection Schemes In Signal Space Methods, Xiaoyi Gu, Deanna Needell, Shenyinying Tu

CMC Faculty Publications and Research

Compressive sensing (CS) is a new technology which allows the acquisition of signals directly in compressed form, using far fewer measurements than traditional theory dictates. Recently, many socalled signal space methods have been developed to extend this body of work to signals sparse in arbitrary dictionaries rather than orthonormal bases. In doing so, CS can be utilized in a much broader array of practical settings. Often, such approaches often rely on the ability to optimally project a signal onto a small number of dictionary atoms. Such optimal, or even approximate, projections have been difficult to derive theoretically. Nonetheless, it has …

Convergence Properties Of The Randomized Extended Gauss-Seidel And Kaczmarz Methods, Anna Ma, Deanna Needell, Aaditya Ramdas

CMC Faculty Publications and Research

The Kaczmarz and Gauss-Seidel methods both solve a linear system Xβ=y by iteratively refining the solution estimate. Recent interest in these methods has been sparked by a proof of Strohmer and Vershynin which shows the randomized Kaczmarz method converges linearly in expectation to the solution. Lewis and Leventhal then proved a similar result for the randomized Gauss-Seidel algorithm. However, the behavior of both methods depends heavily on whether the system is under or overdetermined, and whether it is consistent or not. Here we provide a unified theory of both methods, their variants for these different settings, and draw connections between …

On Montel And Montel–Popoviciu Theorems In Several Variables, Asuman Güven Aksoy, Jose M. Almira

CMC Faculty Publications and Research

We present an elementary proof of a general version of Montel’s theorem in several variables which is based on the use of tensor product polynomial interpolation. We also prove a Montel-Popoviciu’s type theorem for functions f:R^d→Rf:Rd→R for d > 1. Furthermore, our proof of this result is also valid for the case d = 1, differing in several points from Popoviciu’s original proof. Finally, we demonstrate that our results are optimal.

Rows Vs. Columns: Randomized Kaczmarz Or Gauss-Seidel For Ridge Regression, Ahmed Hefny, Deanna Needell, Aaditya Ramdas

CMC Faculty Publications and Research

The Kaczmarz and Gauss-Seidel methods aim to solve a linear m × n system Xβ = y by iteratively refining the solution estimate; the former uses random rows of X to update β given the corresponding equations and the latter uses random columns of X to update corresponding coordinates in β. Interest in these methods was recently revitalized by a proof of Strohmer and Vershynin showing linear convergence in expectation for a randomized Kaczmarz method variant (RK), and a similar result for the randomized Gauss-Seidel algorithm (RGS) was later proved by Lewis and Leventhal. Recent work unified the analysis of …

Compressive Sensing With Redundant Dictionaries And Structured Measurements, Felix Krahmer, Deanna Needell, Rachel Ward

CMC Faculty Publications and Research

Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary D. This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary, if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the D-restricted isometry property (D-RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in D. While many classes of random matrices are known to satisfy such conditions, such matrices …

One-Bit Compressive Sensing With Partial Support, Phillip North, Deanna Needell

CMC Faculty Publications and Research

The Compressive Sensing framework maintains relevance even when the available measurements are subject to extreme quantization, as is exemplified by the so-called one-bit compressed sensing framework which aims to recover a signal from measurements reduced to only their sign-bit. In applications, it is often the case that we have some knowledge of the structure of the signal beforehand, and thus would like to leverage it to attain more accurate and efficient recovery. This work explores avenues for incorporating such partial support information into the one-bit setting. Experimental results demonstrate that newly proposed methods of this work yield improved signal recovery …

On Lattices Generated By Finite Abelian Groups, Albrecht Böttcher, Lenny Fukshansky, Stephan Ramon Garcia, Hiren Maharaj

CMC Faculty Publications and Research

This paper is devoted to the study of lattices generated by finite Abelian groups. Special species of such lattices arise in the exploration of elliptic curves over finite fields. In the case where the generating group is cyclic, they are also known as the Barnes lattices. It is shown that for every finite Abelian group with the exception of the cyclic group of order four these lattices have a basis of minimal vectors. Another result provides an improvement of a recent upper bound by M. Sha for the covering radius in the case of the Barnes lattices. Also discussed are …

Stability Of Ideal Lattices From Quadratic Number Fields, Lenny Fukshansky

CMC Faculty Publications and Research

We study semi-stable ideal lattices coming from real quadratic number fields. Specifically, we demonstrate infinite families of semi-stable and unstable ideal lattices of trace type, establishing explicit conditions on the canonical basis of an ideal that ensure stability; in particular, our result implies that an ideal lattice of trace type coming from a real quadratic field is semi-stable with positive probability. We also briefly discuss the connection between stability and well-roundedness of Euclidean lattices.

Height Bounds On Zeros Of Quadratic Forms Over Q-Bar, Lenny Fukshansky

CMC Faculty Publications and Research

In this paper we establish three results on small-height zeros of quadratic polynomials over Q. For a single quadratic form in N ≥ 2 variables on a subspace of Q N , we prove an upper bound on the height of a smallest nontrivial zero outside of an algebraic set under the assumption that such a zero exists. For a system of k quadratic forms on an L-dimensional subspace of Q N , N ≥ L ≥ k(k+1) 2 + 1, we prove existence of a nontrivial simultaneous small-height zero. For a system of one or two inhomogeneous quadratic and …

Permutation Invariant Lattices, Lenny Fukshansky, Stephan Ramon Garcia, Xun Sun

CMC Faculty Publications and Research

We say that a Euclidean lattice in Rn is permutation invariant if its automorphism group has non-trivial intersection with the symmetric group Sn, i.e., if the lattice is closed under the action of some non-identity elements of Sn. Given a fixed element τ ∈ Sn, we study properties of the set of all lattices closed under the action of τ: we call such lattices τ-invariant. These lattices naturally generalize cyclic lattices introduced by Micciancio in [8, 9], which we previously studied in [1]. Continuing our investigation, we discuss some basic properties of permutation invariant lattices, in particular proving that the …

Spherical 2-Designs And Lattices From Abelian Groups, Albrecht Böttcher, Lenny Fukshansky, Stephan Ramon Garcia, Hiren Maharaj

CMC Faculty Publications and Research

We consider lattices generated by finite Abelian groups. The main result says that such a lattice is strongly eutactic, which means the normalized minimal vectors of the lattice form a spherical 2-design, if and only if the group is of odd order or if it is a power of the group of order 2. This result also yields a criterion for the appropriately normalized minimal vectors to constitute a uniform normalized tight frame.

Exponential Decay Of Reconstruction Error From Binary Measurements Of Sparse Signals, Richard Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, Mary Wootters

CMC Faculty Publications and Research

Binary measurements arise naturally in a variety of statistical and engineering applications. They may be inherent to the problem—e.g., in determining the relationship between genetics and the presence or absence of a disease—or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by onebit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements …

Near Oracle Performance And Block Analysis Of Signal Space Greedy Methods, Raja Giryes, Deanna Needell

CMC Faculty Publications and Research

Compressive sampling (CoSa) is a new methodology which demonstrates that sparse signals can be recovered from a small number of linear measurements. Greedy algorithms like CoSaMP have been designed for this recovery, and variants of these methods have been adapted to the case where sparsity is with respect to some arbitrary dictionary rather than an orthonormal basis. In this work we present an analysis of the so-called Signal Space CoSaMP method when the measurements are corrupted with mean-zero white Gaussian noise. We establish near-oracle performance for recovery of signals sparse in some arbitrary dictionary. In addition, we analyze the block …

Linear Convergence Of Stochastic Iterative Greedy Algorithms With Sparse Constraints, Nam Nguyen, Deanna Needell, Tina Woolf

CMC Faculty Publications and Research

Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and co-variance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which …

Lattices From Elliptic Curves Over Finite Fields, Lenny Fukshansky, Hiren Maharaj

CMC Faculty Publications and Research

In their well known book Tsfasman and Vladut introduced a construction of a family of function field lattices from algebraic curves over finite fields, which have asymptotically good packing density in high dimensions. In this paper we study geometric properties of lattices from this construction applied to elliptic curves. In particular, we determine the generating sets, conditions for well-roundedness and a formula for the number of minimal vectors. We also prove a bound on the covering radii of these lattices, which improves on the standard inequalities.