BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Felix Krahmer

Felix Krahmer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITmath.NANumerical Analysismath.FAmath.OCData Structures and Algorithmseess.SPMachine Learningmath.CAmath.PRComputational Engineering, Finance, and ScienceComputational GeometryComputer Visionmath.AGmath.DSmath.MGmath.SPmath.STStatistics TheorySymbolic Computation

Catalog footprint

What is connected

32works
21topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

32 published item(s)

preprint2022arXiv

Non-intrusive surrogate modelling using sparse random features with applications in crashworthiness analysis

Efficient surrogate modelling is a key requirement for uncertainty quantification in data-driven scenarios. In this work, a novel approach of using Sparse Random Features for surrogate modelling in combination with self-supervised dimensionality reduction is described. The method is compared to other methods on synthetic and real data obtained from crashworthiness analyses. The results show a superiority of the here described approach over state of the art surrogate modelling techniques, Polynomial Chaos Expansions and Neural Networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On recovery guarantees for angular synchronization

The angular synchronization problem of estimating a set of unknown angles from their known noisy pairwise differences arises in various applications. It can be reformulated as a optimization problem on graphs involving the graph Laplacian matrix. We consider a general, weighted version of this problem, where the impact of the noise differs between different pairs of entries and some of the differences are erased completely; this version arises for example in ptychography. We study two common approaches for solving this problem, namely eigenvector relaxation and semidefinite convex relaxation. Although some recovery guarantees are available for both methods, their performance is either unsatisfying or restricted to the unweighted graphs. We close this gap, deriving recovery guarantees for the weighted problem that are completely analogous to the unweighted version.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The Surprising Benefits of Hysteresis in Unlimited Sampling: Theory, Algorithms and Experiments

The Unlimited Sensing Framework (USF) was recently introduced to overcome the sensor saturation bottleneck in conventional digital acquisition systems. At its core, the USF allows for high-dynamic-range (HDR) signal reconstruction by converting a continuous-time signal into folded, low-dynamic-range (LDR), modulo samples. HDR reconstruction is then carried out by algorithmic unfolding of the folded samples. In hardware, however, implementing an ideal modulo folding requires careful calibration, analog design and high precision. At the interface of theory and practice, this paper explores a computational sampling strategy that relaxes strict hardware requirements by compensating them via a novel, mathematically guaranteed recovery method. Our starting point is a generalized model for USF. The generalization relies on two new parameters modeling hysteresis and folding transients} in addition to the modulo threshold. Hysteresis accounts for the mismatch between the reset threshold and the amplitude displacement at the folding time and we refer to a continuous transition period in the implementation of a reset as folding transient. Both these effects are motivated by our hardware experiments and also occur in previous, domain-specific applications. We show that the effect of hysteresis is beneficial for the USF and we leverage it to derive the first recovery guarantees in the context of our generalized USF model. Additionally, we show how the proposed recovery can be directly generalized for the case of lower sampling rates. Our theoretical work is corroborated by hardware experiments that are based on a hysteresis enabled, modulo ADC testbed comprising off-the-shelf electronic components. Thus, by capitalizing on a collaboration between hardware and algorithms, our paper enables an end-to-end pipeline for HDR sampling allowing more flexible hardware implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Unlimited Sampling from Theory to Practice: Fourier-Prony Recovery and Prototype ADC

Following the Unlimited Sampling strategy to alleviate the omnipresent dynamic range barrier, we study the problem of recovering a bandlimited signal from point-wise modulo samples, aiming to connect theoretical guarantees with hardware implementation considerations. Our starting point is a class of non-idealities that we observe in prototyping an unlimited sampling based analog-to-digital converter. To address these non-idealities, we provide a new Fourier domain recovery algorithm. Our approach is validated both in theory and via extensive experiments on our prototype analog-to-digital converter, providing the first demonstration of unlimited sampling for data arising from real hardware, both for the current and previous approaches. Advantages of our algorithm include that it is agnostic to the modulo threshold and it can handle arbitrary folding times. We expect that the end-to-end realization studied in this paper will pave the path for exploring the unlimited sampling methodology in a number of real world applications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions

In this paper a sublinear time algorithm is presented for the reconstruction of functions that can be represented by just few out of a potentially large candidate set of Fourier basis functions in high spatial dimensions, a so-called high-dimensional sparse fast Fourier transform. In contrast to many other such algorithms, our method works for arbitrary candidate sets and does not make additional structural assumptions on the candidate set. Our transform significantly improves upon the other approaches available for such a general framework in terms of the scaling of the sample complexity. Our algorithm is based on sampling the function along multiple rank-1 lattices with random generators. Combined with a dimension-incremental approach, our method yields a sparse Fourier transform whose computational complexity only grows mildly in the dimension and can hence be efficiently computed even in high dimensions. Our theoretical analysis establishes that any Fourier $s$-sparse function can be accurately reconstructed with high probability. This guarantee is complemented by several numerical tests demonstrating the high efficiency and versatile applicability for the exactly sparse case and also for the compressible case.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Complex phase retrieval from subgaussian measurements

Phase retrieval refers to the problem of reconstructing an unknown vector $x_0 \in \mathbb{C}^n$ or $x_0 \in \mathbb{R}^n $ from $m$ measurements of the form $y_i = \big\vert \langle ξ^{\left(i\right)}, x_0 \rangle \big\vert^2 $, where $ \left\{ ξ^{\left(i\right)} \right\}^m_{i=1} \subset \mathbb{C}^m $ are known measurement vectors. While Gaussian measurements allow for recovery of arbitrary signals provided the number of measurements scales at least linearly in the number of dimensions, it has been shown that ambiguities may arise for certain other classes of measurements $ \left\{ ξ^{\left(i\right)} \right\}^{m}_{i=1}$ such as Bernoulli measurements or Fourier measurements. In this paper, we will prove that even when a subgaussian vector $ ξ^{\left(i\right)} \in \mathbb{C}^m $ does not fulfill a small-ball probability assumption, the PhaseLift method is still able to reconstruct a large class of signals $x_0 \in \mathbb{R}^n$ from the measurements. This extends recent work by Krahmer and Liu from the real-valued to the complex-valued case. However, our proof strategy is quite different and we expect some of the new proof ideas to be useful in several other measurement scenarios as well. We then extend our results $x_0 \in \mathbb{C}^n $ up to an additional assumption which, as we show, is necessary.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Recovery Guarantees for One-Bit Compressed Sensing on Manifolds

This paper studies the problem of recovering a signal from one-bit compressed sensing measurements under a manifold model; that is, assuming that the signal lies on or near a manifold of low intrinsic dimension. We provide a convex recovery method based on the Geometric Multi-Resolution Analysis and prove recovery guarantees with a near-optimal scaling in the intrinsic manifold dimension. Our method is the first tractable algorithm with such guarantees for this setting. The results are complemented by numerical experiments confirming the validity of our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the convex geometry of blind deconvolution and matrix completion

Low-rank matrix recovery from structured measurements has been a topic of intense study in the last decade and many important problems like matrix completion and blind deconvolution have been formulated in this framework. An important benchmark method to solve these problems is to minimize the nuclear norm, a convex proxy for the rank. A common approach to establish recovery guarantees for this convex program relies on the construction of a so-called approximate dual certificate. However, this approach provides only limited insight in various respects. Most prominently, the noise bounds exhibit seemingly suboptimal dimension factors. In this paper we take a novel, more geometric viewpoint to analyze both the matrix completion and the blind deconvolution scenario. We find that for both these applications the dimension factors in the noise bounds are not an artifact of the proof, but the problems are intrinsically badly conditioned. We show, however, that bad conditioning only arises for very small noise levels: Under mild assumptions that include many realistic noise levels we derive near-optimal error estimates for blind deconvolution under adversarial noise.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Sets

Johnson-Lindenstrauss embeddings are widely used to reduce the dimension and thus the processing time of data. To reduce the total complexity, also fast algorithms for applying these embeddings are necessary. To date, such fast algorithms are only available either for a non-optimal embedding dimension or up to a certain threshold on the number of data points. We address a variant of this problem where one aims to simultaneously embed larger subsets of the data set. Our method follows an approach by Nelson: A subsampled Hadamard transform maps points into a space of lower, but not optimal dimension. Subsequently, a random matrix with independent entries projects to an optimal embedding dimension. For subsets whose size scales at least polynomially in the ambient dimension, the complexity of this method comes close to the number of operations just to read the data under mild assumptions on the size of the data set that are considerably less restrictive than in previous works. We also prove a lower bound showing that subsampled Hadamard matrices alone cannot reach an optimal embedding dimension. Hence, the second embedding cannot be omitted.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Predicting sparse circle maps from their dynamics

The problem of identifying a dynamical system from its dynamics is of great importance for many applications. Recently it has been suggested to impose sparsity models for improved recovery performance. In this paper, we provide recovery guarantees for such a scenario. More precisely, we show that ergodic systems on the circle described by sparse trigonometric polynomials can be recovered from a number of samples scaling near-linearly in the sparsity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparse Harmonic Transforms: A New Class of Sublinear-time Algorithms for Learning Functions of Many Variables

We develop fast and memory efficient numerical methods for learning functions of many variables that admit sparse representations in terms of general bounded orthonormal tensor product bases. Such functions appear in many applications including, e.g., various Uncertainty Quantification(UQ) problems involving the solution of parametric PDE that are approximately sparse in Chebyshev or Legendre product bases. We expect that our results provide a starting point for a new line of research on sublinear-time solution techniques for UQ applications of the type above which will eventually be able to scale to significantly higher-dimensional problems than what are currently computationally feasible. More concretely, let $B$ be a finite Bounded Orthonormal Product Basis (BOPB) of cardinality $|B|=N$. We will develop methods that approximate any function $f$ that is sparse in the BOPB, that is, $f:\mathcal{D}\subset R^D\rightarrow C$ of the form $f(\mathbf{x})=\sum_{b\in S}c_b\cdot b(\mathbf{x})$ with $S\subset B$ of cardinality $|S| =s\ll N$. Our method has a runtime of just $(s\log N)^{O(1)}$, uses only $(s\log N)^{O(1)}$ function evaluations on a fixed and nonadaptive grid, and not more than $(s\log N)^{O(1)}$ bits of memory. For $s\ll N$, the runtime $(s\log N)^{O(1)}$ will be less than what is required to simply enumerate the elements of the basis $B$; thus our method is the first approach applicable in a general BOPB framework that falls into the class referred to as "sublinear-time". This and the similarly reduced sample and memory requirements set our algorithm apart from previous works based on standard compressive sensing algorithms such as basis pursuit which typically store and utilize full intermediate basis representations of size $Ω(N)$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Empirical Chaos Processes and Blind Deconvolution

This paper investigates conditions under which certain kinds of systems of bilinear equations have a unique structured solution. In particular, we look at when we can recover vectors $\boldsymbol{w},\boldsymbol{q}$ from observations of the form \[ y_{\ell} = <\boldsymbol{w},\boldsymbol{b}_{\ell}><\boldsymbol{c}_{\ell},\boldsymbol{q}>, \quad \ell = 1,\ldots,L, \] where $\boldsymbol{b}_\ell,\boldsymbol{c}_\ell$ are known. We show that if $\boldsymbol{w}\in\mathbb{C}^{M_1}$ and $\boldsymbol{q}\in\mathbb{C}^{M_2}$ are sparse, with no more than $K$ and $N$ nonzero entries, respectively, and the $\boldsymbol{b}_\ell,\boldsymbol{c}_\ell$ are generic, selected as independent Gaussian random vectors, then $\boldsymbol{w},\boldsymbol{q}$ are uniquely determined from \[ L \geq \mathrm{Const}\cdot (K+N)\log^5(M_1M_2) \] such equations with high probability. The key ingredient in our analysis is a uniform probabilistic bound on how far a random process of the form \[Z(\boldsymbol{X}) = \sum_{\ell=1}^L|\boldsymbol{b}_\ell^*\boldsymbol{X}\boldsymbol{c}_\ell|^2 \] deviates from its mean over a set of structured matrices $\boldsymbol{X}\in\mathcal{X}$. As both $\boldsymbol{b}_\ell$ and $\boldsymbol{c}_\ell$ are random, this is a specialized type of $4$th order chaos; we refer to $Z(\boldsymbol{X})$ as an {\em empirical chaos process}. Bounding this process yields a set of general conditions for when the map $\boldsymbol{X}\rightarrow \{\boldsymbol{b}_\ell^*\boldsymbol{X}\boldsymbol{c}_\ell\}_{\ell=1}^L$ is a restricted isometry over the set of matrices $\mathcal{X}$. The conditions are stated in terms of general geometric properties of the set $\mathcal{X}$, and are explicitly computed for the case where $\mathcal{X}$ is the set of matrices that are simultaneously sparse and low rank.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems

We study identifiability for bilinear inverse problems under sparsity and subspace constraints. We show that, up to a global scaling ambiguity, almost all such maps are injective on the set of pairs of sparse vectors if the number of measurements $m$ exceeds $2(s_1+s_2)-2$, where $s_1$ and $s_2$ denote the sparsity of the two input vectors, and injective on the set of pairs of vectors lying in known subspaces of dimensions $n_1$ and $n_2$ if $m\geq 2(n_1+n_2)-4$. We also prove that both these bounds are tight in the sense that one cannot have injectivity for a smaller number of measurements. Our proof technique draws from algebraic geometry. As an application we derive optimal identifiability conditions for the deconvolution problem, thus improving on recent work of Li et al. [1].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Homotopy Method Revisited: Computing Solution Paths of $\ell_1$-Regularized Problems

$ \ell_1 $-regularized linear inverse problems are frequently used in signal processing, image analysis, and statistics. The correct choice of the regularization parameter $ t \in \mathbb{R}_{\geq 0} $ is a delicate issue. Instead of solving the variational problem for a fixed parameter, the idea of the homotopy method is to compute a complete solution path $ u(t) $ as a function of $ t $. In a celebrated paper by Osborne, Presnell, and Turlach, it has been shown that the computational cost of this approach is often comparable to the cost of solving the corresponding least squares problem. Their analysis relies on the one-at-a-time condition, which requires that different indices enter or leave the support of the solution at distinct regularization parameters. In this paper, we introduce a generalized homotopy algorithm based on a nonnegative least squares problem, which does not require such a condition, and prove its termination after finitely many steps. At every point of the path, we give a full characterization of all possible directions. To illustrate our results, we discuss examples in which the standard homotopy method either fails or becomes infeasible. To the best of our knowledge, our algorithm is the first to provably compute a full solution path for an arbitrary combination of an input matrix and a data vector.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Novel Compressed Sensing Scheme for Photoacoustic Tomography

Speeding up the data acquisition is one of the central aims to advance tomographic imaging. On the one hand, this reduces motion artifacts due to undesired movements, and on the other hand this decreases the examination time for the patient. In this article, we propose a new scheme for speeding up the data collection process in photoacoustic tomography. Our proposal is based on compressed sensing and reduces acquisition time and system costs while maintaining image quality. As measurement data we use random combinations of pressure values that we use to recover a complete set of pressure data prior to the actual image reconstruction. We obtain theoretical recovery guarantees for our compressed sensing scheme and support the theory by reconstruction results on simulated data as well as on experimental data.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A unified framework for linear dimensionality reduction in L1

For a family of interpolation norms $\| \cdot \|_{1,2,s}$ on $\mathbb{R}^n$, we provide a distribution over random matrices $Φ_s \in \mathbb{R}^{m \times n}$ parametrized by sparsity level $s$ such that for a fixed set $X$ of $K$ points in $\mathbb{R}^n$, if $m \geq C s \log(K)$ then with high probability, $\frac{1}{2} \| x \|_{1,2,s} \leq \| Φ_s (x) \|_1 \leq 2 \| x\|_{1,2,s}$ for all $x\in X$. Several existing results in the literature reduce to special cases of this result at different values of $s$: for $s=n$, $\| x\|_{1,2,n} \equiv \| x \|_{1}$ and we recover that dimension reducing linear maps can preserve the $\ell_1$-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For $s=1$, $\|x \|_{1,2,1} \equiv \| x \|_{2}$, and we recover an $\ell_2 / \ell_1$ variant of the Johnson-Lindenstrauss Lemma for Gaussian random matrices. Finally, if $x$ is $s$-sparse, then $\| x \|_{1,2,s} = \| x \|_1$ and we recover that $s$-sparse vectors in $\ell_1^n$ embed into $\ell_1^{\mathcal{O}(s \log(n))}$ via sparse random matrix constructions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An arithmetic-geometric mean inequality for products of three matrices

Consider the following noncommutative arithmetic-geometric mean inequality: given positive-semidefinite matrices $\mathbf{A}_1, \dots, \mathbf{A}_n$, the following holds for each integer $m \leq n$: $$ \frac{1}{n^m}\sum_{j_1, j_2, \dots, j_m = 1}^{n} ||| \mathbf{A}_{j_1} \mathbf{A}_{j_2} \dots \mathbf{A}_{j_m} ||| \geq \frac{(n-m)!}{n!} \sum_{\substack{j_1, j_2, \dots, j_m = 1 \\ \text{all distinct}}}^{n} ||| \mathbf{A}_{j_1} \mathbf{A}_{j_2} \dots \mathbf{A}_{j_m} |||,$$ where $||| \cdot |||$ denotes a unitarily invariant norm, including the operator norm and Schatten p-norms as special cases. While this inequality in full generality remains a conjecture, we prove that the inequality holds for products of up to three matrices, $m \leq 3$. The proofs for $m = 1,2$ are straightforward; to derive the proof for $m=3$, we appeal to a variant of the classic Araki-Lieb-Thirring inequality for permutations of matrix products.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Compressive Sensing with Redundant Dictionaries and Structured Measurements

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 are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the $D$-RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary $D$. We also extend this analysis to allow for weighted sparse expansions. Consequently, we arrive at compressive sensing recovery guarantees for structured measurements and redundant dictionaries, opening the door to a wide array of practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Noise-shaping Quantization Methods for Frame-based and Compressive Sampling Systems

Noise shaping refers to an analog-to-digital conversion methodology in which quantization error is arranged to lie mostly outside the signal spectrum by means of oversampling and feedback. Recently it has been successfully applied to more general redundant linear sampling and reconstruction systems associated with frames as well as non-linear systems associated with compressive sampling. This chapter reviews some of the recent progress in this subject.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An RIP-based approach to $ΣΔ$ quantization for compressed sensing

In this paper, we provide a new approach to estimating the error of reconstruction from $ΣΔ$ quantized compressed sensing measurements. Our method is based on the restricted isometry property (RIP) of a certain projection of the measurement matrix. Our result yields simple proofs and a slight generalization of the best-known reconstruction error bounds for Gaussian and subgaussian measurement matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantization and Compressive Sensing

Quantization is an essential step in digitizing signals, and, therefore, an indispensable component of any modern acquisition system. This book chapter explores the interaction of quantization and compressive sensing and examines practical quantization strategies for compressive acquisition systems. Specifically, we first provide a brief overview of quantization and examine fundamental performance bounds applicable to any quantization approach. Next, we consider several forms of scalar quantizers, namely uniform, non-uniform, and 1-bit. We provide performance bounds and fundamental analysis, as well as practical quantizer designs and reconstruction algorithms that account for quantization. Furthermore, we provide an overview of Sigma-Delta ($ΣΔ$) quantization in the compressed sensing context, and also discuss implementation issues, recovery algorithms and performance bounds. As we demonstrate, proper accounting for quantization and careful quantizer design has significant impact in the performance of a compressive acquisition system.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Structured random measurements in signal processing

Compressed sensing and its extensions have recently triggered interest in randomized signal acquisition. A key finding is that random measurements provide sparse signal reconstruction guarantees for efficient and stable algorithms with a minimal number of samples. While this was first shown for (unstructured) Gaussian random measurement matrices, applications require certain structure of the measurements leading to structured random measurement matrices. Near optimal recovery guarantees for such structured measurements have been developed over the past years in a variety of contexts. This article surveys the theory in three scenarios: compressed sensing (sparse recovery), low rank matrix recovery, and phaseless estimation. The random measurement matrices to be considered include random partial Fourier matrices, partial random circulant matrices (subsampled convolutions), matrix completion, and phase estimation from magnitudes of Fourier type measurements. The article concludes with a brief discussion of the mathematical techniques for the analysis of such structured random measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fast Subspace Approximation via Greedy Least-Squares

In this note, we develop fast and deterministic dimensionality reduction techniques for a family of subspace approximation problems. Let $P\subset \mathbbm{R}^N$ be a given set of $M$ points. The techniques developed herein find an $O(n \log M)$-dimensional subspace that is guaranteed to always contain a near-best fit $n$-dimensional hyperplane $\mathcal{H}$ for $P$ with respect to the cumulative projection error $(\sum_{{\bf x} \in P} \| {\bf x} - Π_\mathcal{H} {\bf x} \|^p_2)^{1/p}$, for any chosen $p > 2$. The deterministic algorithm runs in $\tilde{O} (MN^2)$-time, and can be randomized to run in only $\tilde{O} (MNn)$-time while maintaining its error guarantees with high probability. In the case $p = \infty$ the dimensionality reduction techniques can be combined with efficient algorithms for computing the John ellipsoid of a data set in order to produce an $n$-dimensional subspace whose maximum $\ell_2$-distance to any point in the convex hull of $P$ is minimized. The resulting algorithm remains $\tilde{O} (MNn)$-time. In addition, the dimensionality reduction techniques developed herein can also be combined with other existing subspace approximation algorithms for $2 < p \leq \infty$ - including more accurate algorithms based on convex programming relaxations - in order to reduce their runtimes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Local sampling and approximation of operators with bandlimited Kohn-Nirenberg symbols

Recent sampling theorems allow for the recovery of operators with bandlimited Kohn-Nirenberg symbols from their response to a single discretely supported identifier signal. The available results are inherently non-local. For example, we show that in order to recover a bandlimited operator precisely, the identifier cannot decay in time nor in frequency. Moreover, a concept of local and discrete representation is missing from the theory. In this paper, we develop tools that address these shortcomings. We show that to obtain a local approximation of an operator, it is sufficient to test the operator on a truncated and mollified delta train, that is, on a compactly supported Schwarz class function. To compute the operator numerically, discrete measurements can be obtained from the response function which are localized in the sense that a local selection of the values yields a local approximation of the operator. Central to our analysis is to conceptualize the meaning of localization for operators with bandlimited Kohn-Nirenberg symbol.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing

Suppose that the collection $\{e_i\}_{i=1}^m$ forms a frame for $\R^k$, where each entry of the vector $e_i$ is a sub-Gaussian random variable. We consider expansions in such a frame, which are then quantized using a Sigma-Delta scheme. We show that an arbitrary signal in $\R^k$ can be recovered from its quantized frame coefficients up to an error which decays root-exponentially in the oversampling rate $m/k$. Here the quantization scheme is assumed to be chosen appropriately depending on the oversampling rate and the quantization alphabet can be coarse. The result holds with high probability on the draw of the frame uniformly for all signals. The crux of the argument is a bound on the extreme singular values of the product of a deterministic matrix and a sub-Gaussian frame. For fine quantization alphabets, we leverage this bound to show polynomial error decay in the context of compressed sensing. Our results extend previous results for structured deterministic frame expansions and Gaussian compressed sensing measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Stable and robust sampling strategies for compressive imaging

In many signal processing applications, one wishes to acquire images that are sparse in transform domains such as spatial finite differences or wavelets using frequency domain samples. For such applications, overwhelming empirical evidence suggests that superior image reconstruction can be obtained through variable density sampling strategies that concentrate on lower frequencies. The wavelet and Fourier transform domains are not incoherent because low-order wavelets and low-order frequencies are correlated, so compressive sensing theory does not immediately imply sampling strategies and reconstruction guarantees. In this paper we turn to a more refined notion of coherence -- the so-called local coherence -- measuring for each sensing vector separately how correlated it is to the sparsity basis. For Fourier measurements and Haar wavelet sparsity, the local coherence can be controlled and bounded explicitly, so for matrices comprised of frequencies sampled from a suitable inverse square power-law density, we can prove the restricted isometry property with near-optimal embedding dimensions. Consequently, the variable-density sampling strategy we provide allows for image reconstructions that are stable to sparsity defects and robust to measurement noise. Our results cover both reconstruction by $\ell_1$-minimization and by total variation minimization. The local coherence framework developed in this paper should be of independent interest in sparse recovery problems more generally, as it implies that for optimal sparse recovery results, it suffices to have bounded \emph{average} coherence from sensing basis to sparsity basis -- as opposed to bounded maximal coherence -- as long as the sampling strategy is adapted accordingly.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Suprema of Chaos Processes and the Restricted Isometry Property

We present a new bound for suprema of a special type of chaos processes indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time-frequency structured random matrices. In both cases the required condition on the number $m$ of rows in terms of the sparsity $s$ and the vector length $n$ is $m \gtrsim s \log^2 s \log^2 n$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sparsity and spectral properties of dual frames

We study sparsity and spectral properties of dual frames of a given finite frame. We show that any finite frame has a dual with no more than $n^2$ non-vanishing entries, where $n$ denotes the ambient dimension, and that for most frames no sparser dual is possible. Moreover, we derive an expression for the exact sparsity level of the sparsest dual for any given finite frame using a generalized notion of spark. We then study the spectral properties of dual frames in terms of singular values of the synthesis operator. We provide a complete characterization for which spectral patterns of dual frames are possible for a fixed frame. For many cases, we provide simple explicit constructions for dual frames with a given spectrum, in particular, if the constraint on the dual is that it be tight.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimally Sparse Frames

Frames have established themselves as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. However, when the signal dimension is large, the computation of the frame measurements of a signal typically requires a large number of additions and multiplications, and this makes a frame decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we focus on frames in finite-dimensional Hilbert spaces and introduce sparsity for such frames as a new paradigm. In our terminology, a sparse frame is a frame whose elements have a sparse representation in an orthonormal basis, thereby enabling low-complexity frame decompositions. To introduce a precise meaning of optimality, we take the sum of the numbers of vectors needed of this orthonormal basis when expanding each frame vector as sparsity measure. We then analyze the recently introduced algorithm Spectral Tetris for construction of unit norm tight frames and prove that the tight frames generated by this algorithm are in fact optimally sparse with respect to the standard unit vector basis. Finally, we show that even the generalization of Spectral Tetris for the construction of unit norm frames associated with a given frame operator produces optimally sparse frames.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

SqFreeEVAL: An (almost) optimal real-root isolation algorithm

Let f be a univariate polynomial with real coefficients, f in R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm. The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+ln d)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits. Our proof uses two amortization-based techniques: First, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Optimal Family of Exponentially Accurate One-Bit Sigma-Delta Quantization Schemes

Sigma-Delta modulation is a popular method for analog-to-digital conversion of bandlimited signals that employs coarse quantization coupled with oversampling. The standard mathematical model for the error analysis of the method measures the performance of a given scheme by the rate at which the associated reconstruction error decays as a function of the oversampling ratio $λ$. It was recently shown that exponential accuracy of the form $O(2^{-rλ})$ can be achieved by appropriate one-bit Sigma-Delta modulation schemes. By general information-entropy arguments $r$ must be less than 1. The current best known value for $r$ is approximately 0.088. The schemes that were designed to achieve this accuracy employ the "greedy" quantization rule coupled with feedback filters that fall into a class we call "minimally supported". In this paper, we study the minimization problem that corresponds to optimizing the error decay rate for this class of feedback filters. We solve a relaxed version of this problem exactly and provide explicit asymptotics of the solutions. From these relaxed solutions, we find asymptotically optimal solutions of the original problem, which improve the best known exponential error decay rate to $r \approx 0.102$. Our method draws from the theory of orthogonal polynomials; in particular, it relates the optimal filters to the zero sets of Chebyshev polynomials of the second kind.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Lower bounds for the error decay incurred by coarse quantization schemes

Several analog-to-digital conversion methods for bandlimited signals used in applications, such as Sigma Delta quantization schemes, employ coarse quantization coupled with oversampling. The standard mathematical model for the error accrued from such methods measures the performance of a given scheme by the rate at which the associated reconstruction error decays as a function of the oversampling ratio L > 1. It was recently shown that exponential accuracy of the form O(2(-r L)) can be achieved by appropriate one-bit Sigma Delta modulation schemes. However, the best known achievable rate constants r in this setting differ significantly from the general information theoretic lower bound. In this paper, we provide the first lower bound specific to coarse quantization, thus narrowing the gap between existing upper and lower bounds. In particular, our results imply a quantitative correspondence between the maximal signal amplitude and the best possible error decay rate. Our method draws from the theory of large deviations.

0 citations0 reviewsNo code linkedOpen access