An approximate sparse recovery system in ℓ 1 norm consists of parameters k , ϵ, N ; an m -by- N measurement Φ; and a recovery algorithm R . Given a vector, x , the system approximates x by xˆ = R (Φ x ), which must satisfy ‖ xˆ- x ‖ 1 ≤ (1+ϵ)‖ x - x k ‖ 1 . We consider the “for all” model, in which a single matrix Φ, possibly “constructed” non-explicitly using the probabilistic method, is used for all signals x . The best existing sublinear algorithm by Porat and Strauss [2012] uses O (ϵ −3 k log ( N / k )) measurements and runs in time O ( k 1 − α N α ) for any constant α > 0. In this article, we improve the number of measurements to O (ϵ − 2 k log ( N / k )), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O ( k 1+β poly(log N ,1/ϵ)), with a modest restriction that k ⩽ N 1 − α and ϵ ⩽ (log k /log N ) γ for any constants α, β, γ > 0. When k ⩽ log c N for some c > 0, the runtime is reduced to O ( k poly( N ,1/ϵ)). With no restrictions on ϵ, we have an approximation recovery system with m = O ( k /ϵlog ( N / k )((log N /log k ) γ + 1/ϵ)) measurements. The overall architecture of this algorithm is similar to that of Porat and Strauss [2012] in that we repeatedly use a weak recovery system (with varying parameters) to obtain a top-level recovery algorithm. The weak recovery system consists of a two-layer hashing procedure (or with two unbalanced expanders for a deterministic algorithm). The algorithmic innovation is a novel encoding procedure that is reminiscent of network coding and that reflects the structure of the hashing stages. The idea is to encode the signal position index i by associating it with a unique message m i , which will be encoded to a longer message m ′ i (in contrast to Porat and Strauss [2012] in which the encoding is simply the identity). Portions of the message m ′ i correspond to repetitions of the hashing, and we use a regular expander graph to encode the linkages among these portions. The decoding or recovery algorithm consists of recovering the portions of the longer messages m ′ i and then decoding to the original messages m i , all the while ensuring that corruptions can be detected and/or corrected. The recovery algorithm is similar to list recovery introduced in Indyk et al. [2010] and used in Gilbert et al. [2013]. In our algorithm, the messages { m i } are independent of the hashing, which enables us to obtain a better result.

An approximate sparse recovery system in ℓ1 norm makes a small number of measurements of a noisy vector with at most k large entries and recovers those heavy hitters approximately. Formally, it consists of parameters N, k, ∊, an m-by-N measurement matrix, Φ, and a decoding algorithm, D. Given a vector, x, where xk denotes the optimal k-term approximation to x, the system approximates x by , which must satisfy Among the goals in designing such systems are minimizing the number m of measurements and the runtime of the decoding algorithm, D. We consider the “forall” model, in which a single matrix Φ, possibly “constructed” non-explicitly using the probabilistic method, is used for all signals x. Many previous papers have provided algorithms for this problem. But all such algorithms that use the optimal number m = O(k log(N/k)) of measurements require superlinear time Ω(N log(N/k)). In this paper, we give the first algorithm for this problem that uses the optimum number of measurements (up to constant factors) and runs in sublinear time o(N) when k is sufficiently less than N. Specifically, for any positive integer ℓ, our approach uses time O(ℓ5 ∊−3k(N/k)1/ℓ) and uses m = O(ℓ8 ∊−3k log (N/k)) measurements, with access to a data structure requiring space and preprocessing time O(ℓNk0.2/∊).

A Euclidean approximate sparse recovery system consists of parameters $k,N$, an m-by-N measurement matrix, $\bm{\Phi}$, and a decoding algorithm, $\mathcal{D}$. Given a vector, ${\mathbf x}$, the system approximates ${\mathbf x}$ by $\widehat {\mathbf x}=\mathcal{D}(\bm{\Phi} {\mathbf x})$, which must satisfy $|\widehat {\mathbf x} - {\mathbf x}|_2\le C |{\mathbf x} - {\mathbf x}_k|_2$, where ${\mathbf x}_k$ denotes the optimal k-term approximation to ${\mathbf x}$. (The output $\widehat{\mathbf x}$ may have more than k terms.) For each vector ${\mathbf 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 $k\log^{O(1)} N$, matching a lower bound up to a polylog$(N)$ factor. We also consider the encode time (i.e., the time to multiply $\bm{\Phi}$ by x), the time to update measurements (i.e., the time to multiply $\bm{\Phi}$ by a 1-sparse x), and the robustness and stability of the algorithm (resilience to noise before and after the measurements). Our encode and update times are optimal up to $\log(k)$ factors. The columns of $\bm{\Phi}$ have at most $O(\log^2(k)\log(N/k))$ nonzeros, each of which can be found in constant time. Our full result, a fully polynomial randomized approximation scheme, is as follows. If ${\mathbf x}={\mathbf x}_k+\nu_1$, where $\nu_1$ and $\nu_2$ (below) are arbitrary vectors (regarded as noise), then setting $\widehat {\mathbf x} = \mathcal{D}(\Phi {\mathbf x} + \nu_2)$, and for properly normalized $\bm{\Phi}$, we get $\left|{\mathbf x} - \widehat {\mathbf x}\right|_2^2 \le (1+\epsilon)\left|\nu_1\right|_2^2 + \epsilon\left|\nu_2\right|_2^2$ using $O((k/\epsilon)\log(N/k))$ measurements and $(k/\epsilon)\log^{O(1)}(N)$ time for decoding.

A Euclidean approximate sparse recovery system consists of parameters k,N, an m-by-N measurement matrix, Φ, and a decoding algorithm, D. Given a vector, x, the system approximates x by ^x=D(Φ x), which must satisfy ||x - x||2≤ C ||x - xk||2, where xk denotes the optimal k-term approximation to x. (The output ^x may have more than k terms). 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, D.

The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of counter-based algorithms (including the popular and very space-efficient Frequent and SpacesSaving algorithms) provides much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining tail. This shows that counter-based methods are the most space-efficient (in fact, space-optimal) algorithms having this strong error bound. This tail guarantee allows these algorithms to solve the sparse recovery problem. Here, the goal is to recover a faithful representation of the vector of frequencies, f . We prove that using space O ( k ), the algorithms construct an approximation f * to the frequency vector f so that the L 1 error ∥∥ f −∥ f *∥ 1 is close to the best possible error min f ′ ∥ f ′ − f ∥ 1 , where f′ ranges over all vectors with at most k non-zero entries. This improves the previously best known space bound of about O ( k log n ) for streams without element deletions (where n is the size of the domain from which stream elements are drawn). Other consequences of the tail guarantees are results for skewed (Zipfian) data, and guarantees for accuracy of merging multiple summarized streams.

The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of "counter-based algorithms" (including the popular and very space-efficient FREQUENT and SPACESAVING algorithms) provide much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining "tail." This shows that counter-based methods are the most space-efficient (in fact, space-optimal) algorithms having this strong error bound.

In this paper we explore several fundamental bounds for a compressive sampling system which uses the Fourier sampling algorithm of Gilbert et al. Beginning with the theoretical bounds on the number of samples necessary to reconstruct high fidelity approximations of input signals, we refine those theoretical bounds with empirical values in several practical input models. We show that the performance is consistent with traditional sampling systems, and, in certain cases, much better.

In this paper, we successfully demonstrate the feasibility of hardware implementation of a sub-Nyquist random sampling based analog to information converter (RS-AIC). The RS-AIC is based on the theory of information recovery from random samples using an efficient information recovery algorithm to compute the spectrogram of the signal. Our RS-AIC enables sub-Nyquist acquisition and processing of wideband signals that are sparse in a local Fourier representation. Results from our RS-AIC hardware implementation demonstrate successful reconstruction of signals that are sampled at half the Nyquist-rate while maintaining up to a 51 dB signal-to-noise ratio (SNR), which is equivalent to an 8.5 bit resolution analog to digital converter.

This project aims to reduce the time required to attain more detailed scans of small interesting regions present in a quick first-pass sample image. In particular, we concentrate on high fidelity imaging of small sample features via hyperspectral Raman imaging (e.g., small scale compositional variations in bone tissue). The current standard procedure for high quality hyperspectral Raman imaging of small sample features consists of four steps: first-pass imaging, detail identification, planning, and finally detail imaging. traditionally, detail imaging and planning have been carried out manually by human personnel - after acquiring some quick low-quality data in first-pass imaging, a researcher looks for interesting features (detail identification) and decides how to acquire higher-quality data for the interesting features (planning), which is done in the final detail imaging phase. In this paper we discuss automating the detail identification and planning steps, resulting in a decrease of the procedure's total integration time. We fix an arbitrary way to automate detail identification and compare several different planning methods. Our primary result is a method guaranteed to return a least cost (e.g., minimum integration time/number of scans) detail image under a general cost model. Because of their generality, the methodologies developed here may prove widely useful to basic biomedical scientists as well as to researchers in the pharmaceutical industry.

In a wide variety of imaging applications (especially medical imaging), we obtain a partial set or subset of the Fourier transform of an image. From these Fourier measurements, we want to reconstruct the entire original image. Convex optimization is a powerful, recent solution to this problem. Unfortunately, convex optimization in its myriad of implementations is computationally expensive and may be impractical for large images or for multiple images. Furthermore, some of these techniques assume that the image has a sparse gradient (i.e., that the gradient of the image consists of a few nonzero pixel values) or that the gradient is highly compressible. In this paper, we demonstrate that we can recover such images with GradientOMP, an efficient algorithm based upon Orthogonal Matching Pursuit (OMP), more effectively than with convex optimization. We compare both the qualitative and quantitative performance of this algorithm to the optimization techniques.

Compressed Sensing is a new paradigm for acquiring the compressible signals that arise in many applications. These signals can be approximated using an amount of information much smaller than the nominal dimension of the signal. Traditional approaches acquire the entire signal and process it to extract the information. The new approach acquires a small number of nonadaptive linear measurements of the signal and uses sophisticated algorithms to determine its information content. Emerging technologies can compute these general linear measurements of a signal at unit cost per measurement.

Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. Furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. In this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call secure approximations. We start by extending standard definitions of secure (exact) computation to the setting of secure approximations. Our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. We then study the complexity of specific secure approximation problems. In particular, we obtain a sublinear-communication protocol for securely approximating the Hamming distance and a polynomial-time protocol for securely approximating the permanent and related #P-hard problems.

A simple sparse approximation problem requests an approximation of a given input signal as a linear combination of T elementary signals drawn from a large, linearly dependent collection. An important generalization is simultaneous sparse approximation. Now one must approximate several input signals at once using different linear combinations of the same T elementary signals. This formulation appears, for example, when analyzing multiple observations of a sparse signal that have been contaminated with noise. A new approach to this problem is presented here: a greedy pursuit algorithm called simultaneous orthogonal matching pursuit. The paper proves that the algorithm calculates simultaneous approximations whose error is within a constant factor of the optimal simultaneous approximation error. This result requires that the collection of elementary signals be weakly correlated, a property that is also known as incoherence. Numerical experiments demonstrate that the algorithm often succeeds, even when the inputs do not meet the hypotheses of the proof.

In this paper, we present new algorithms for dynamically computing quantiles of a relation subject to insert as well as delete operations. At the core of our algorithms lies a small-space multiresolution representation of the underlying data distribution based on random subset sums or RSSs. These RSSs are updated with every insert and delete operation. When quantiles are demanded, we use these RSSs to estimate quickly, without having to access the data, all the quantiles, each guaranteed to be accurate to within user-specified precision. While quantiles have found many uses in databases, in this paper, our focus is primarily on network management applications that monitor the distribution of active sessions in the network. Our examples are drawn both from the telephony and the IP network, where the goal is to monitor the distribution of the length of active calls and IP flows, respectively, over time. For such applications, we propose a new type of histogram that uses RSSs for summarizing the dynamic parts of the distributions while other parts with small volume of sessions are approximated using simple counters.

This paper discusses a new greedy algorithm for solving the sparse approximation problem over quasiincoherent dictionaries. These dictionaries consist of waveforms that are uncorrelated "on average," and they provide a natural generalization of incoherent dictionaries. The algorithm provides strong guarantees on the quality of the approximations it produces, unlike most other methods for sparse approximation. Moreover, very efficient implementations are possible via approximate nearest-neighbor data structures.

We formalize the problem of maintaining time-decaying aggregates and statistics of a data stream: the relative contribution of each data item to the aggregate is scaled down by a factor that depends on, and is non-decreasing with, elapsed time. Time-decaying aggregates are used in applications where the significance of data items decreases over time. We develop storage-efficient algorithms, and establish upper and lower bounds. Surprisingly, even though maintaining decayed aggregates have become a widely-used tool, our work seems to be the first both to explore it formally and to provide storage-efficient algorithms for important families of decay functions, including polynomial decay.

We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of the underlying data. We present general "sketch"-based methods for capturing various linear projections and use them to provide pointwise and rangesum estimation of data streams. These methods use small amounts of space and per-item time while streaming through the data and provide accurate representation as our experiments with real data streams show.

(MATH) A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A3." We give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a B-bucket piecewise-constant representation (histogram) H for A from the sketch, such that ||A—H||≤(1+ε)||A—Hopt||, where the error ||A—H|| is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. The time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly(B,log(N),log||A,1/ε. Our result is obtained in two steps. First we obtain what we call a robust histogram approximation for A, a histogram such that adding a small number of buckets does not help improve the representation quality significantly. From the robust histogram, we cull a histogram of desired accruacy and B buckets in the second step. This technique also provides similar results for Haar wavelet representations, under $\ell_2$ error. Our results have applications in summarizing data distributions fast and succinctly even in distributed settings.

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N, such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0,N), chosen randomly from a (non-product) distribution of our choice, independent of A. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N)log(M)ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.

Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and the monitoring and operations of large systems. In network operations, raw data typically arrive in streams, and decisions must be made by algorithms that make one pass over each stream, throw much of the raw data away, and produce "synopses" or "sketches" for further processing. Moreover, network-generated massive data sets are often distributed: Several different, physically separated network elements may receive or generate data streams that, together, comprise one logical data set; to be of use in operations, the streams must be analyzed locally and their synopses sent to a central operations facility. The enormous scale, distributed nature, and one-pass processing requirement on the data sets of interest must be addressed with new algorithmic techniques. We present one fundamental new technique here: a space-efficient, one-pass algorithm for approximating the L 1 -difference $\sum_i|a_i-b_i|$ between two functions, when the function values a i and b i are given as data streams, and their order is chosen by an adversary. Our main technical innovation, which may be of interest outside the realm of massive data stream algorithmics, is a method of constructing families $\{V_j(s)\}$ of limited-independence random variables that are range-summable, by which we mean that $\sum_{j=0}^{c-1} V_j(s)$ is computable in time polylog(c) for all seeds s. Our L 1 -difference algorithm can be viewed as a "sketching" algorithm, in the sense of [Broder et al., J. Comput. System Sci., 60 (2000), pp. 630--659], and our technique performs better than that of Broder et al. when used to approximate the symmetric difference of two sets with small symmetric difference.

Fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. Hence, there has been a lot of focus on “selectivity estimation”, that is, computing summary statistics on the underlying data and using that to answer aggregate queries fast and to a reasonable approximation. We present two sets of results for range aggregate queries, which are amongst the most common queries.

We introduce resource-bounded betting games and propose a generalization of Lutz's resource-bounded measure in which the choice of the next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudorandom number generators exist, then betting games are equivalent to martingales for measure on E and EXP. However, we construct betting games that succeed on certain classes whose Lutz measures are important open problems: the class of polynomial-time Turing-complete languages in EXP and its superclass of polynomial-time Turing-autoreducible languages. If an EXP-martingale succeeds on either of these classes, or if betting games have the "finite union property" possessed by Lutz's measure, one obtains the nonrelativizable consequence $\mbox{BPP} \neq \mbox{EXP}$. We also show that if $\mbox{EXP} \neq \mbox{MA}$, then the polynomial-time truth-table-autoreducible languages have Lutz measure zero, whereas if $\mbox{EXP} = \mbox{BPP}$, they have measure one.

We introduce a technique for using an untrusted device, such as a hand-held personal digital assistant or a laptop to perform real financial transactions without a network. We utilize the tamper-resistant nature of smartcards to store value on them and perform probabilistic computations based on user input. We discuss an application of this to gambling. The technique has the properties that the user is guaranteed to make money when he wins and the house is guaranteed to make money when the user loses. 1 Introduction We are currently experiencing a proliferation of lightweight handheld devices, such as the 3Com palm pilot, windows CE devices, and even laptops that weigh under three pounds. Many of these devices are so portable that people have them in their pockets and use them at all times. Our goal is to enable people to utilize these devices during otherwise dead time perhaps at the doctor's office, or in line at the supermarket. We are interested in utilizing the time when the us...

We give a space-efficient, one-pass algorithm for approximating the L/sup 1/ difference /spl Sigma//sub i/|a/sub i/-b/sub i/| between two functions, when the function values a/sub i/ and b/sub i/ are given as data streams, and their order is chosen by an adversary. Our main technical innovation is a method of constructing families {V/sub j/} of limited independence random variables that are range summable by which we mean that /spl Sigma//sub j=0//sup c-1/ V/sub j/(s) is computable in time polylog(c), for all seeds s. These random variable families may be of interest outside our current application domain, i.e., massive data streams generated by communication networks. Our L/sup 1/-difference algorithm can be viewed as a "sketching" algorithm, in the sense of (A. Broder et al., 1998), and our algorithm performs better than that of Broder et al., when used to approximate the symmetric difference of two sets with small symmetric difference.

Resource-bounded measure theory is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have measure zero in Exponential Time. This is a quantitative strengthening of NP/spl ne/P. We show that the analog in P of this hypothesis fails dramatically. In fact, we show that NTIME[n/sup 1/11/] has measure zero in P. These follow as consequences of our main theorem that the collection of languages accepted by constant-depth nearly exponential-size circuits has measure zero at polynomial time. In contrast, we show that the class AC/sup 0//sub 4/[/spl oplus/] of languages accepted by depth-4 polynomial-size circuits with AND, OR, NOT, and PARITY gates does not have measure zero at polynomial time. Our proof is based on techniques from circuit complexity theory and pseudorandom generators.

We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause Lutz's definitions to apply only to classes at least as large as E. We present many of the basic properties of this measure, and use it to explore the class of sets that are hard for BPP. Bennett and Gill showed that almost all sets are hard for BPP; Lutz improved this from Lebesgue measure to measure on ESPACE. We use our measure to improve this still further, showing that for all /spl epsiv/>0, almost every set in E/sub /spl epsiv// is hard for BPP, where E/sub /spl epsiv//=/spl cup//sub /spl delta/>