Source author record

Martin J. Strauss

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms cond-mat.dis-nn cond-mat.stat-mech Information Theory math.IT

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

L2/L2-foreach sparse recovery with low risk

In this paper, we consider the "foreach" sparse recovery problem with failure probability $p$ . The goal of which is to design a distribution over $m \times N$ matrices $Φ$ and a decoding algorithm $\algo$ such that for every $\vx\in\R^N$, we have the following error guarantee with probability at least $1-p$ \[\|\vx-\algo(Φ\vx)\|_2\le C\|\vx-\vx_k\|_2,\] where $C$ is a constant (ideally arbitrarily close to 1) and $\vx_k$ is the best $k$ -sparse approximation of $\vx$. Much of the sparse recovery or compressive sensing literature has focused on the case of either $p = 0$ or $p = Ω(1)$ . We initiate the study of this problem for the entire range of failure probability. Our two main results are as follows: \begin{enumerate} \item We prove a lower bound on $m$ , the number measurements, of $Ω(k\log(n/k)+\log(1/p))$ for $2^{-Θ(N)}\le p <1$ . Cohen, Dahmen, and DeVore \cite{CDD2007:NearOptimall2l2} prove that this bound is tight. \item We prove nearly matching upper bounds for \textit{sub-linear} time decoding. Previous such results addressed only $p = Ω(1)$ . \end{enumerate} Our results and techniques lead to the following corollaries: (i) the first ever sub-linear time decoding $\lolo$ "forall" sparse recovery system that requires a $\log^γ{N}$ extra factor (for some $γ<1$ ) over the optimal $O(k\log(N/k))$ number of measurements, and (ii) extensions of Gilbert et al. \cite{GHRSW12:SimpleSignals} results for information-theoretically bounded adversaries.

preprint2011arXiv

Sublinear Time, Measurement-Optimal, Sparse Recovery For All

An approximate sparse recovery system in ell_1 norm formally consists of parameters N, k, epsilon an m-by-N measurement matrix, Phi, and a decoding algorithm, D. Given a vector, x, where x_k denotes the optimal k-term approximation to x, the system approximates x by hat_x = D(Phi.x), which must satisfy ||hat_x - x||_1 <= (1+epsilon)||x - x_k||_1. Among the goals in designing such systems are minimizing m and the runtime of D. We consider the "forall" model, in which a single matrix Phi is used for all signals x. All previous algorithms that use the optimal number m=O(k log(N/k)) of measurements require superlinear time Omega(N log(N/k)). In this paper, we give the first algorithm for this problem that uses the optimum number of measurements (up to a constant factor) and runs in sublinear time o(N) when k=o(N), assuming access to a data structure requiring space and preprocessing O(N).

preprint2009arXiv

Approximate Sparse Recovery: Optimizing Time and Measurements

An approximate sparse recovery system consists of parameters $k,N$ , an $m$ -by- $N$ measurement matrix, $Φ$ , and a decoding algorithm, $\mathcal{D}$ . Given a vector, $x$ , the system approximates $x$ by $\widehat x =\mathcal{D}(Φx)$ , which must satisfy $\| \widehat x - x\|_2\le C \|x - x_k\|_2$ , where $x_k$ denotes the optimal $k$ -term approximation to $x$ . For each vector $x$ , the system must succeed with probability at least 3/4. Among the goals in designing such systems are minimizing the number $m$ of measurements and the runtime of the decoding algorithm, $\mathcal{D}$ . In this paper, we give a system with $m=O(k \log(N/k))$ measurements--matching a lower bound, up to a constant factor--and decoding time $O(k\log^c N)$ , matching a lower bound up to $\log(N)$ factors. We also consider the encode time (i.e., the time to multiply $Φ$ by $x$ ), the time to update measurements (i.e., the time to multiply $Φ$ by a 1-sparse $x$ ), and the robustness and stability of the algorithm (adding noise before and after the measurements). Our encode and update times are optimal up to $\log(N)$ factors.

preprint2006arXiv

Networks of strong ties

Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be ``trusted''. In this paper we consider transitivity as evidence of strong ties, requiring that each tie can only be used if the individuals on either end also share at least one other contact in common. We examine the effect of removing all non-transitive ties in two real social network data sets. We observe that although some individuals become disconnected, a giant connected component remains, with an average shortest path only slightly longer than that of the original network. We also evaluate the cost of forming transitive ties by deriving the conditions for the emergence and the size of the giant component in a random graph composed entirely of closed triads and the equivalent Erdos-Renyi random graph.

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.