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

Sjoerd Dirksen

Sjoerd Dirksen 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.PRmath.FAData Structures and Algorithmsmath.OAMachine Learningmath.STStatistics TheoryComputational Geometrymath.MGmath.NAmath.RTNumerical Analysis

Catalog footprint

What is connected

17works
14topics
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

17 published item(s)

preprint2022arXiv

Binarized Johnson-Lindenstrauss embeddings

We consider the problem of encoding a set of vectors into a minimal number of bits while preserving information on their Euclidean geometry. We show that this task can be accomplished by applying a Johnson-Lindenstrauss embedding and subsequently binarizing each vector by comparing each entry of the vector to a uniformly random threshold. Using this simple construction we produce two encodings of a dataset such that one can query Euclidean information for a pair of points using a small number of bit operations up to a desired additive error - Euclidean distances in the first case and inner products and squared Euclidean distances in the second. In the latter case, each point is encoded in near-linear time. The number of bits required for these encodings is quantified in terms of two natural complexity parameters of the dataset - its covering numbers and localized Gaussian complexity - and shown to be near-optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Covariance estimation under one-bit quantization

We consider the classical problem of estimating the covariance matrix of a subgaussian distribution from i.i.d. samples in the novel context of coarse quantization, i.e., instead of having full knowledge of the samples, they are quantized to one or two bits per entry. This problem occurs naturally in signal processing applications. We introduce new estimators in two different quantization scenarios and derive non-asymptotic estimation error bounds in terms of the operator norm. In the first scenario we consider a simple, scale-invariant one-bit quantizer and derive an estimation result for the correlation matrix of a centered Gaussian distribution. In the second scenario, we add random dithering to the quantizer. In this case we can accurately estimate the full covariance matrix of a general subgaussian distribution by collecting two bits per entry of each sample. In both scenarios, our bounds apply to masked covariance estimation. We demonstrate the near-optimality of our error bounds by deriving corresponding (minimax) lower bounds and using numerical simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast metric embedding into the Hamming cube

We consider the problem of embedding a subset of $\mathbb{R}^n$ into a low-dimensional Hamming cube in an almost isometric way. We construct a simple, data-oblivious, and computationally efficient map that achieves this task with high probability: we first apply a specific structured random matrix, which we call the double circulant matrix; using that matrix requires linear storage and matrix-vector multiplication can be performed in near-linear time. We then binarize each vector by comparing each of its entries to a random threshold, selected uniformly at random from a well-chosen interval. We estimate the number of bits required for this encoding scheme in terms of two natural geometric complexity parameters of the set - its Euclidean covering numbers and its localized Gaussian complexity. The estimate we derive turns out to be the best that one can hope for - up to logarithmic terms. The key to the proof is a phenomenon of independent interest: we show that the double circulant matrix mimics the behavior of a Gaussian matrix in two important ways. First, it maps an arbitrary set in $\mathbb{R}^n$ into a set of well-spread vectors. Second, it yields a fast near-isometric embedding of any finite subset of $\ell_2^n$ into $\ell_1^m$. This embedding achieves the same dimension reduction as a Gaussian matrix in near-linear time, under an optimal condition - up to logarithmic factors - on the number of points to be embedded. This improves a well-known construction due to Ailon and Chazelle.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sharp estimates on random hyperplane tessellations

We study the problem of generating a hyperplane tessellation of an arbitrary set $T$ in $\mathbb{R}^n$, ensuring that the Euclidean distance between any two points corresponds to the fraction of hyperplanes separating them up to a pre-specified error $δ$. We focus on random gaussian tessellations with uniformly distributed shifts and derive sharp bounds on the number of hyperplanes $m$ that are required. Surprisingly, our lower estimates falsify the conjecture that $m\sim \ell_*^2(T)/δ^2$, where $\ell_*^2(T)$ is the gaussian width of $T$, is optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness

We consider the problem of determining the asymptotic order of the Gelfand numbers of mixed-(quasi-)norm embeddings $\ell^b_p(\ell^d_q) \hookrightarrow \ell^b_r(\ell^d_u)$ given that $p \leq r$ and $q \leq u$, with emphasis on cases with $p\leq 1$ and/or $q\leq 1$. These cases turn out to be related to structured sparsity. We obtain sharp bounds in a number of interesting parameter constellations. Our new matching bounds for the Gelfand numbers of the embeddings of $\ell_1^b(\ell_2^d)$ and $\ell_2^b(\ell_1^d)$ into $\ell_2^b(\ell_2^d)$ imply optimality assertions for the recovery of block-sparse and sparse-in-levels vectors, respectively. In addition, we apply the sharp estimates for $\ell^b_p(\ell^d_q)$-spaces to obtain new two-sided estimates for the Gelfand numbers of multivariate Besov space embeddings in regimes of small mixed smoothness. It turns out that in some particular cases these estimates show the same asymptotic behaviour as in the univariate situation. In the remaining cases they differ at most by a $\log\log$ factor from the univariate bound.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs

We study sparse recovery with structured random measurement matrices having independent, identically distributed, and uniformly bounded rows and with a nontrivial covariance structure. This class of matrices arises from random sampling of bounded Riesz systems and generalizes random partial Fourier matrices. Our main result improves the currently available results for the null space and restricted isometry properties of such random matrices. The main novelty of our analysis is a new upper bound for the expectation of the supremum of a Bernoulli process associated with a restricted isometry constant. We apply our result to prove new performance guarantees for the CORSING method, a recently introduced numerical approximation technique for partial differential equations (PDEs) based on compressive sensing.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the gap between RIP-properties and sparse recovery conditions

We consider the problem of recovering sparse vectors from underdetermined linear measurements via $\ell_p$-constrained basis pursuit. Previous analyses of this problem based on generalized restricted isometry properties have suggested that two phenomena occur if $p\neq 2$. First, one may need substantially more than $s \log(en/s)$ measurements (optimal for $p=2$) for uniform recovery of all $s$-sparse vectors. Second, the matrix that achieves recovery with the optimal number of measurements may not be Gaussian (as for $p=2$). We present a new, direct analysis which shows that in fact neither of these phenomena occur. Via a suitable version of the null space property we show that a standard Gaussian matrix provides $\ell_q/\ell_1$-recovery guarantees for $\ell_p$-constrained basis pursuit in the optimal measurement regime. Our result extends to several heavier-tailed measurement matrices. As an application, we show that one can obtain a consistent reconstruction from uniform scalar quantized measurements in the optimal measurement regime.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Toward a unified theory of sparse dimensionality reduction in Euclidean space

Let $Φ\in\mathbb{R}^{m\times n}$ be a sparse Johnson-Lindenstrauss transform [KN14] with $s$ non-zeroes per column. For a subset $T$ of the unit sphere, $\varepsilon\in(0,1/2)$ given, we study settings for $m,s$ required to ensure $$ \mathop{\mathbb{E}}_Φ\sup_{x\in T} \left|\|Φx\|_2^2 - 1 \right| < \varepsilon , $$ i.e. so that $Φ$ preserves the norm of every $x\in T$ simultaneously and multiplicatively up to $1+\varepsilon$. We introduce a new complexity parameter, which depends on the geometry of $T$, and show that it suffices to choose $s$ and $m$ such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense $Φ$ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dimensionality reduction with subgaussian matrices: a unified theory

We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson-Lindenstrauss type results obtained earlier for specific data sets. In particular, we recover and, in several cases, improve results for sets of sparse and structured sparse vectors, low-rank matrices and tensors, and smooth manifolds. In addition, we establish a new Johnson-Lindenstrauss embedding for data sets taking the form of an infinite union of subspaces of a Hilbert space.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Itô isomorphisms for $L^{p}$-valued Poisson stochastic integrals

Motivated by the study of existence, uniqueness and regularity of solutions to stochastic partial differential equations driven by jump noise, we prove Itô isomorphisms for $L^p$-valued stochastic integrals with respect to a compensated Poisson random measure. The principal ingredients for the proof are novel Rosenthal type inequalities for independent random variables taking values in a (noncommutative) $L^p$-space, which may be of independent interest. As a by-product of our proof, we observe some moment estimates for the operator norm of a sum of independent random matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tail bounds via generic chaining

We modify Talagrand's generic chaining method to obtain upper bounds for all p-th moments of the supremum of a stochastic process. These bounds lead to an estimate for the upper tail of the supremum with optimal deviation parameters. We apply our procedure to improve and extend some known deviation inequalities for suprema of unbounded empirical processes and chaos processes. As an application we give a significantly simplified proof of the restricted isometry property of the subsampled discrete Fourier transform.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Uniform recovery of fusion frame structured sparse signals

We consider the problem of recovering fusion frame sparse signals from incomplete measurements. These signals are composed of a small number of nonzero blocks taken from a family of subspaces. First, we show that, by using a-priori knowledge of a coherence parameter associated with the angles between the subspaces, one can uniformly recover fusion frame sparse signals with a significantly reduced number of vector-valued (sub-)Gaussian measurements via mixed l^1/l^2-minimization. We prove this by establishing an appropriate version of the restricted isometry property. Our result complements previous nonuniform recovery results in this context, and provides stronger stability guarantees for noisy measurements and approximately sparse signals. Second, we determine the minimal number of scalar-valued measurements needed to uniformly recover all fusion frame sparse signals via mixed l^1/l^2-minimization. This bound is achieved by scalar-valued subgaussian measurements. In particular, our result shows that the number of scalar-valued subgaussian measurements cannot be further reduced using knowledge of the coherence parameter. As a special case it implies that the best known uniform recovery result for block sparse signals using subgaussian measurements is optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Noncommutative Boyd interpolation theorems

We present a new, elementary proof of Boyd's interpolation theorem. Our approach naturally yields a noncommutative version of this result and even allows for the interpolation of certain operators on l^1-valued noncommutative symmetric spaces. By duality we may interpolate several well-known noncommutative maximal inequalities. In particular we obtain a version of Doob's maximal inequality and the dual Doob inequality for noncommutative symmetric spaces. We apply our results to prove the Burkholder-Davis-Gundy and Burkholder-Rosenthal inequalities for noncommutative martingales in these spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Poisson stochastic integration in Banach spaces

We prove new upper and lower bounds for Banach space-valued stochastic integrals with respect to a compensated Poisson random measure. Our estimates apply to Banach spaces with non-trivial martingale (co)type and extend various results in the literature. We also develop a Malliavin framework to interpret Poisson stochastic integrals as vector-valued Skorohod integrals, and prove a Clark-Ocone representation formula.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Weak-type interpolation for noncommutative maximal operators

We prove a Boyd-type interpolation result for noncommutative maximal operators of restricted weak type. Our result positively answers an open question posed recently by Bekjan, Chen and Osekowski. As a special case, we find a restricted weak type version of the noncommutative Marcinkiewicz interpolation theorem, due to Junge and Xu, with interpolation constant of optimal order.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Crossed products of Banach algebras. I

We construct a crossed product Banach algebra from a Banach algebra dynamical system $(A,G,α)$ and a given uniformly bounded class $R$ of continuous covariant Banach space representations of that system. If $A$ has a bounded left approximate identity, and $R$ consists of non-degenerate continuous covariant representations only, then the non-degenerate bounded representations of the crossed product are in bijection with the non-degenerate $R$-continuous covariant representations of the system. This bijection, which is the main result of the paper, is also established for involutive Banach algebra dynamical systems and then yields the well-known representation theoretical correspondence for the crossed product $C^*$-algebra as commonly associated with a $C^*$-algebra dynamical system as a special case. Taking the algebra $A$ to be the base field, the crossed product construction provides, for a given non-empty class of Banach spaces, a Banach algebra with a relatively simple structure and with the property that its non-degenerate contractive representations in the spaces from that class are in bijection with the isometric strongly continuous representations of $G$ in those spaces. This generalizes the notion of a group $C^*$-algebra, and may likewise be used to translate issues concerning group representations in a class of Banach spaces to the context of a Banach algebra, simpler than $L^1(G)$, where more functional analytic structure is present.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Some remarks on noncommutative Khintchine inequalities

Normalized free semi-circular random variables satisfy an upper Khintchine inequality in $L_\infty$. We show that this implies the corresponding upper Khintchine inequality in any noncommutative Banach function space. As applications, we obtain a very simple proof of a well-known interpolation result for row and column operator spaces and, moreover, answer an open question on noncommutative moment inequalities concerning a paper by Bekjan and Chen.

0 citations0 reviewsNo code linkedOpen access