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, …