Author name cluster

Yi Li 0002

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

1 author row

ICML Conference 2025 Conference Paper

Faster Approximation Algorithms for k-Center via Data Reduction

Arnold Filtser
Shaofeng H. -C. Jiang
Yi Li 0002
Anurag Murty Naredla
Ioannis Psarros
Qiaoyuan Yang
Qin Zhang 0001

We study efficient algorithms for the Euclidean $k$-Center problem, focusing on the regime of large $k$. We take the approach of data reduction by considering $\alpha$-coreset, which is a small subset $S$ of the dataset $P$ such that any $\beta$-approximation on $S$ is an $(\alpha + \beta)$-approximation on $P$. We give efficient algorithms to construct coresets whose size is $k \cdot o(n)$, which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time $O(1)$-approximation when $k = n^c$ for any $0 < c < 1$. We validate the performance of our coresets on real-world datasets with large $k$, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to $4$ times, while still achieving similar clustering cost. Technically, one of our coreset results is based on a new efficient construction of consistent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces.

ICML Conference 2025 Conference Paper

Robust Sparsification via Sensitivity

Chansophea Wathanak In
Yi Li 0002
David P. Woodruff
Xuan Wu 0002

Robustness to outliers is important in machine learning. Many classical problems, including subspace embedding, clustering, and low-rank approximation, lack scalable, outlier-resilient algorithms. This paper considers machine learning problems of the form $\min_{x\in \mathbb{R}^d} F(x)$, where $F(x)=\sum_{i=1}^n F_i(x)$, and their robust counterparts $\min_{x\in\mathbb{R}^d} F^{(m)}(x)$, where $F^{(m)}(x)$ denotes the sum of all but the $m$ largest $F_i(x)$ values. We develop a general framework for constructing $\epsilon$-coresets for such robust problems, where an $\epsilon$-coreset is a weighted subset of functions $\{F_1(x), …, F_n(x)\}$ that provides a $(1+\epsilon)$-approximation to $F(x)$. Specifically, if the original problem $F$ has total sensitivity $T$ and admits a vanilla $\epsilon$-coreset of size $S$, our algorithm constructs an $\epsilon$-coreset of size $\tilde{O}(\frac{mT}{\epsilon})+S$ for the robust objective $F^{(m)}$. This coreset size can be shown to be near-tight for $\ell_2$ subspace embedding. Our coreset algorithm has scalable running time and leads to new or improved algorithms for the robust optimization problems. Empirical evaluations demonstrate that our coresets outperform uniform sampling on real-world data sets.

ICLR Conference 2024 Conference Paper

One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models

Sheng-Jun Huang
Yi Li 0002
Yiming Sun
Ying-Peng Tang

Active learning (AL) for multiple target models aims to reduce labeled data querying while effectively training multiple models concurrently. Existing AL algorithms often rely on iterative model training, which can be computationally expensive, particularly for deep models. In this paper, we propose a one-shot AL method to address this challenge, which performs all label queries without repeated model training. Specifically, we extract different representations of the same dataset using distinct network backbones, and actively learn the linear prediction layer on each representation via an $\ell_p$-regression formulation. The regression problems are solved approximately by sampling and reweighting the unlabeled instances based on their maximum Lewis weights across the representations. An upper bound on the number of samples needed is provided with a rigorous analysis for $p\in [1, +\infty)$. Experimental results on 11 benchmarks show that our one-shot approach achieves competitive performances with the state-of-the-art AL methods for multiple target models.

ICLR Conference 2024 Conference Paper

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms

Yi Li 0002
Honghao Lin
David P. Woodruff

We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more expensive low-rank approximation computation will be. The matrix case concerns the Frobenius norm and the task is to approximate the $k$-residual $\|A - A_k\|_F$ of the input matrix $A$ within a $(1+\epsilon)$-factor, where $A_k$ is the optimal rank-$k$ approximation. We provide a tight bound of $\Theta(k^2/\epsilon^4)$ on the size of bilinear sketches, which have the form of a matrix product $SAT$. This improves the previous $O(k^2/\epsilon^6)$ upper bound in (Andoni et al. SODA 2013) and gives the first non-trivial lower bound, to the best of our knowledge. In our algorithm, our sketching matrices $S$ and $T$ can both be sparse matrices, allowing for a very fast update time. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. For the vector case, we consider the $\ell_p$-norm for $p>2$, where the task is to approximate the $k$-residual $\|x - x_k\|_p$ up to a constant factor, where $x_k$ is the optimal $k$-sparse approximation to $x$. Such vector norms are frequently studied in the data stream literature and are useful for finding frequent items or so-called heavy hitters. We establish an upper bound of $O(k^{2/p}n^{1-2/p}\operatorname{poly}(\log n))$ for constant $\epsilon$ on the dimension of a linear sketch for this problem. Our algorithm can be extended to the $\ell_p$ sparse recovery problem with the same sketching dimension, which seems to be the first such bound for $p > 2$. We also show an $\Omega(k^{2/p}n^{1-2/p})$ lower bound for the sparse recovery problem, which is tight up to a $\mathrm{poly}(\log n)$ factor.

ICLR Conference 2023 Conference Paper

Learning the Positions in CountSketch

Yi Li 0002
Honghao Lin
Simin Liu
Ali Vakilian
David P. Woodruff

We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g., low-rank approximation and regression. In the learning-based sketching paradigm proposed by Indyk et al., the sketch matrix is found by choosing a random sparse matrix, e.g., CountSketch, and then the values of its non-zero entries are updated by running gradient descent on a training data set. Despite the growing body of work on this paradigm, a noticeable omission is that the locations of the non-zero entries of previous algorithms were fixed, and only their values were learned. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries. Our first proposed algorithm is based on a greedy algorithm. However, one drawback of the greedy algorithm is its slower training time. We fix this issue and propose approaches for learning a sketching matrix for both low-rank approximation and Hessian approximation for second-order optimization. The latter is helpful for a range of constrained optimization problems, such as LASSO and matrix estimation with a nuclear norm constraint. Both approaches achieve good accuracy with a fast running time. Moreover, our experiments suggest that our algorithm can still reduce the error significantly even if we only have a very limited number of training matrices.

SODA Conference 2023 Conference Paper

The ℓ p -Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

Yi Li 0002
Honghao Lin
David P. Woodruff

In the ℓ p -subspace sketch problem, we are given an n × d matrix A with n > d, and asked to build a small memory data structure Q ( A, ε ) so that, for any query vector x ∈ ℝ d, we can output a number in given only Q(A, ε ). This problem is known to require bits of memory for d = Ω(log (1/ε)). However, for d = o (log(l/ε)), no data structure lower bounds were known. Small constant values of d are particularly important for estimating point queries for support vector machines (SVMs) in a stream (Andoni et al. 2020), where only tight bounds for d = 1 were known. We resolve the memory required to solve the ℓ p -subspace sketch problem for any constant d and integer p, showing that it is bits and words, where the Õ(·) notation hides poly(log(1/ε)) factors. This shows that one can beat the Ω(ε -2 ) lower bound, which holds for d = Ω(log(1/ε)), for any constant d. Further, we show how to implement the upper bound in a single pass stream, with an additional multiplicative poly(log log n) factor and an additive poly(log n ) cost in the memory. Our bounds extend to loss functions other than the ℓ p -norm, and notably they apply to point queries for SVMs with additive error, where we show an optimal bound of for every constant d. This is a near-quadratic improvement over the lower bound of Andoni et al. Further, previous upper bounds for SVM point query were noticeably lacking: for d =1 the bound was Õ(e -1/2 ) and for d = 2 the bound was Õ (ε -4//5 ), but all existing techniques failed to give any upper bound better than Õ (ε -2 ) for any other value of d. Our techniques, which rely on a novel connection to low dimensional techniques from geometric functional analysis, completely close this gap.

ICML Conference 2022 Conference Paper

Online Active Regression

Cheng Chen 0015
Yi Li 0002
Yiming Sun

Active regression considers a linear regression problem where the learner receives a large number of data points but can only observe a small number of labels. Since online algorithms can deal with incremental training data and take advantage of low computational cost, we consider an online extension of the active regression problem: the learner receives data points one by one and immediately decides whether it should collect the corresponding labels. The goal is to efficiently maintain the regression of received data points with a small budget of label queries. We propose novel algorithms for this problem under $\ell_p$ loss where $p\in[1, 2]$. To achieve a $(1+\epsilon)$-approximate solution, our proposed algorithms only requires $\tilde{\mathcal{O}}(d/poly(\epsilon))$ queries of labels. The numerical results verify our theoretical results and show that our methods have comparable performance with offline active regression algorithms.

ICML Conference 2021 Conference Paper

Single Pass Entrywise-Transformed Low Rank Approximation

Yifei Jiang
Yi Li 0002
Yiming Sun
Jiaxin Wang
David P. Woodruff

In applications such as natural language processing or computer vision, one is given a large $n \times n$ matrix $A = (a_{i, j})$ and would like to compute a matrix decomposition, e. g. , a low rank approximation, of a function $f(A) = (f(a_{i, j}))$ applied entrywise to $A$. A very important special case is the likelihood function $f\left( A \right ) = \log{\left( \left| a_{ij}\right| +1\right)}$. A natural way to do this would be to simply apply $f$ to each entry of $A$, and then compute the matrix decomposition, but this requires storing all of $A$ as well as multiple passes over its entries. Recent work of Liang et al. shows how to find a rank-$k$ factorization to $f(A)$ using only $n \cdot \poly(\eps^{-1}k\log n)$ words of memory, with overall error $10\|f(A)-[f(A)]_k\|_F^2 + \poly(\epsilon/k) \|f(A)\|_{1, 2}^2$, where $[f(A)]_k$ is the best rank-$k$ approximation to $f(A)$ and $\|f(A)\|_{1, 2}^2$ is the square of the sum of Euclidean lengths of rows of $f(A)$. Their algorithm uses $3$ passes over the entries of $A$. The authors pose the open question of obtaining an algorithm with $n \cdot \poly(\eps^{-1}k\log n)$ words of memory using only a single pass over the entries of $A$. In this paper we resolve this open question, obtaining the first single-pass algorithm for this problem and for the same class of functions $f$ studied by Liang et al. Moreover, our error is $\|f(A)-[f(A)]_k\|_F^2 + \poly(\epsilon/k) \|f(A)\|_F^2$, where $\|f(A)\|_F^2$ is the sum of squares of Euclidean lengths of rows of $f(A)$. Thus our error is significantly smaller, as it removes the factor of $10$ and also $\|f(A)\|_F^2 \leq \|f(A)\|_{1, 2}^2$.

ICML Conference 2020 Conference Paper

Input-Sparsity Low Rank Approximation in Schatten Norm

Yi Li 0002
David P. Woodruff

We give the first input-sparsity time algorithms for the rank-$k$ low rank approximation problem in every Schatten norm. Specifically, for a given $n\times n$ matrix $A$, our algorithm computes $Y, Z\in \R^{n\times k}$, which, with high probability, satisfy $\|A-YZ^T\|_p \leq (1+\eps)\|A-A_k\|_p$, where $\|M\|_p = \left (\sum_{i=1}^n \sigma_i(M)^p \right )^{1/p}$ is the Schatten $p$-norm of a matrix $M$ with singular values $\sigma_1(M), \ldots, \sigma_n(M)$, and where $A_k$ is the best rank-$k$ approximation to $A$. Our algorithm runs in time $\tilde{O}(\nnz(A) + n^{\alpha_p}\poly(k/\eps))$, where $\alpha_p = 1$ for $p\in [1, 2)$ and $\alpha_p = 1 + (\omega-1)(1-2/p)$ for $p>2$ and $\omega \approx 2. 374$ is the exponent of matrix multiplication. For the important case of $p = 1$, which corresponds to the more “robust” nuclear norm, we obtain $\tilde{O}(\nnz(A) + n \cdot \poly(k/\epsilon))$ time, which was previously only known for the Frobenius norm $(p = 2)$. Moreover, since $\alpha_p < \omega$ for every $p$, our algorithm has a better dependence on $n$ than that in the singular value decomposition for every $p$. Crucial to our analysis is the use of dimensionality reduction for Ky-Fan $p$-norms.

ICLR Conference 2020 Conference Paper

Learning-Augmented Data Stream Algorithms

Tanqiu Jiang
Yi Li 0002
Honghao Lin
Yisong Ruan
David P. Woodruff

The data stream model is a fundamental model for processing massive data sets with limited memory and fast processing time. Recently Hsu et al. (2019) incorporated machine learning techniques into the data stream model in order to learn relevant patterns in the input data. Such techniques were encapsulated by training an oracle to predict item frequencies in the streaming model. In this paper we explore the full power of such an oracle, showing that it can be applied to a wide array of problems in data streams, sometimes resulting in the first optimal bounds for such problems. Namely, we apply the oracle to counting distinct elements on the difference of streams, estimating frequency moments, estimating cascaded aggregates, and estimating moments of geometric data streams. For the distinct elements problem, we obtain the first memory-optimal algorithms. For estimating the $p$-th frequency moment for $0 < p < 2$ we obtain the first algorithms with optimal update time. For estimating the $p$-the frequency moment for $p > 2$ we obtain a quadratic saving in memory. We empirically validate our results, demonstrating also our improvements in practice.

ICML Conference 2020 Conference Paper

Nearly Linear Row Sampling Algorithm for Quantile Regression

Yi Li 0002
Ruosong Wang
Lin F. Yang
Hanrui Zhang 0001

We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm whose sampling complexity has at least cubic dependence on the dimensionality. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs. Our main technical contribution is to show that Lewis weights sampling, which has been used in row sampling algorithms for $\ell_p$ norms, can also be applied in row sampling algorithms for a variety of loss functions. We complement our theoretical results by experiments to demonstrate the practicality of our approach.

SODA Conference 2020 Conference Paper

Tight Bounds for the Subspace Sketch Problem with Applications

Yi Li 0002
Ruosong Wang
David P. Woodruff

In the subspace sketch problem one is given an n × d matrix A with O (log( nd )) bit entries, and would like to compress it in an arbitrary way to build a small space data structure Q p, so that for any given x ϵ ℝ d, with probability at least 2/3, one has Q p ( x ) = (1 ± ε )|| Ax || p, where p ≥ 0 and the randomness is over the construction of Q p. The central question is: How many bits are necessary to store Q p? This problem has applications to the communication of approximating the number of non-zeros in a matrix product, the size of coresets in projective clustering, the memory of streaming algorithms for regression in the row-update model, and embedding subspaces of L p in functional analysis. A major open question is the dependence on the approximation factor ε. We show if p ≥ 0 is not a positive even integer and d = Ω(log(1/ ε )), then ( ε −2 · d ) bits are necessary. On the other hand, if p is a positive even integer, then there is an upper bound of O ( d p log( nd )) bits independent of ε. Our results are optimal up to logarithmic factors, and show in particular that one cannot compress A to O ( d ) “directions” ν 1, …, ν o ( d ), such that for any x, || Ax || 1 can be well-approximated from 〈 ν 1, x 〉, …, 〈 ν O ( d ), x 〉. Our lower bound rules out arbitrary functions of these inner products (and in fact arbitrary data structures built from A ), and thus rules out the possibility of a singular value decomposition for ℓ 1 in a very strong sense. Indeed, as ε → 0, for p = 1 the space complexity becomes arbitrarily large, while for p = 2 it is at most O ( d 2 log( nd )). As corollaries of our main lower bound, we obtain new lower bounds for a wide range of applications, including the above, which in many cases are optimal.

SODA Conference 2019 Conference Paper

Testing Matrix Rank, Optimally

Maria-Florina Balcan
Yi Li 0002
David P. Woodruff
Hongyang Zhang 0001

We show that for the problem of testing if a matrix has rank at most d, or requires changing an ∊-fraction of entries to have rank at most d, there is a non-adaptive query algorithm making Õ ( d 2 /∊) queries. Our algorithm works for any field. This improves upon the previous Õ ( d 2 /∊ 2 ) bound (Krauthgamer and Sasson, SODA ′03), and bypasses an Ω( d 2 /∊ 2 ) lower bound of (Li, Wang, and Woodruff, KDD ′14) which holds if the algorithm is required to read a submatrix. Our algorithm is the first such algorithm which does not read a submatrix, and instead reads a carefully selected non-adaptive pattern of entries in rows and columns of A. We complement our algorithm with a matching query complexity lower bound for non-adaptive testers over any field. We also give tight bounds of Õ ( d 2 ) queries in the sensing model for which query access comes in the form of 〈 X i, A 〉: = tr( X i ⊺ A ); perhaps surprisingly these bounds do not depend on ∊. Testing rank is only one of many tasks in determining if a matrix has low intrinsic dimensionality. We next develop a novel property testing framework for testing numerical properties of a real-valued matrix A more generally, which includes the stable rank, Schatten- p norms, and SVD entropy. Specifically, we propose a bounded entry model, where A is required to have entries bounded by 1 in absolute value. Such a model provides a meaningful framework for testing numerical quantities and avoids trivialities caused by single entries being arbitrarily large. It is also well-motivated by recommendation systems. We give upper and lower bounds for a wide range of problems in this model, and discuss connections to the sensing model above. We obtain several results for estimating the operator norm that may be of independent interest. For example, we show that if the stable rank is constant, ‖ A ‖ F = Ω( n ), and the singular value gap σ 1 ( A )/ σ 2 ( A ) = (1/ ∊ ) γ for any constant γ > 0, then the operator norm can be estimated up to a (1 ± ∊ )-factor non-adaptively by querying O (1/ ∊ 2 ) entries. This should be contrasted to adaptive methods such as the power method, or previous non-adaptive sampling schemes based on matrix Bernstein inequalities which read a 1/ ∊ 2 × 1/ ∊ 2 submatrix and thus make Ω(1/ ∊ 4 ) queries. Similar to our non-adaptive algorithm for testing rank, our scheme instead reads a carefully selected pattern of entries.

ICML Conference 2018 Conference Paper

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order

Vladimir Braverman
Stephen R. Chestnut
Robert Krauthgamer
Yi Li 0002
David P. Woodruff
Lin F. Yang

A central problem in mining massive data streams is characterizing which functions of an underlying frequency vector can be approximated efficiently. Given the prevalence of large scale linear algebra problems in machine learning, recently there has been considerable effort in extending this data stream problem to that of estimating functions of a matrix. This setting generalizes classical problems to the analogous ones for matrices. For example, instead of estimating frequent-item counts, we now wish to estimate “frequent-direction” counts. A related example is to estimate norms, which now correspond to estimating a vector norm on the singular values of the matrix. Despite recent efforts, the current understanding for such matrix problems is considerably weaker than that for vector problems. We study a number of aspects of estimating matrix norms in a stream that have not previously been considered: (1) multi-pass algorithms, (2) algorithms that see the underlying matrix one row at a time, and (3) time-efficient algorithms. Our multi-pass and row-order algorithms use less memory than what is provably required in the single-pass and entrywise-update models, and thus give separations between these models (in terms of memory). Moreover, all of our algorithms are considerably faster than previous ones. We also prove a number of lower bounds, and obtain for instance, a near-complete characterization of the memory required of row-order algorithms for estimating Schatten $p$-norms of sparse matrices. We complement our results with numerical experiments.

STOC Conference 2016 Conference Paper

On approximating functions of the singular values in a stream

Yi Li 0002
David P. Woodruff

For any real number p > 0, we nearly completely characterize the space complexity of estimating || A || p p = ∑ i =1 n σ i p for n × n matrices A in which each row and each column has O (1) non-zero entries and whose entries are presented one at a time in a data stream model. Here the σ i are the singular values of A , and when p ≥ 1, || A || p p is the p -th power of the Schatten p -norm. We show that when p is not an even integer, to obtain a (1+є)-approximation to || A || p p with constant probability, any 1-pass algorithm requires n 1− g (є) bits of space, where g (є) → 0 as є → 0 and є > 0 is a constant independent of n . However, when p is an even integer, we give an upper bound of n 1−2/ p (є −1 log n ) bits of space, which holds even in the turnstile data stream model. The latter is optimal up to (є −1 log n ) factors.

SODA Conference 2014 Conference Paper

On Sketching Matrix Norms and the Top Singular Vector

Yi Li 0002
Huy L. Nguyen 0001
David P. Woodruff

Sketching is a prominent algorithmic tool for processing large data. In this paper, we study the problem of sketching matrix norms. We consider two sketching models. The first is bilinear sketching, in which there is a distribution over pairs of r × n matrices S and n × s matrices T such that for any fixed n × n matrix A, from S · A · T one can approximate ‖A‖ p up to an approximation factor α ≥ 1 with constant probability, where ‖ A ‖ p is a matrix norm. The second is general linear sketching, in which there is a distribution over linear maps, such that for any fixed n × n matrix A, interpreting it as a vector in ℝ n, from L ( A ) one can approximate ‖ A ‖ p up to a factor α. We study some of the most frequently occurring matrix norms, which correspond to Schatten p -norms for p ∊ {0, 1, 2, ∞ }. The p -th Schatten norm of a rank- r matrix A is defined to be, where σ 1, …, σ r are the singular values of A. When p = 0, ‖ A ‖ 0 is defined to be the rank of A. The cases p = 1, 2, and ∞ correspond to the trace, Frobenius, and operator norms, respectively. For bilinear sketches we show: 1. For p = 00 any sketch must have r · s = Ω( n 2 / α 4 ) dimensions. This matches an upper bound of Andoni and Nguyen (SODA, 2013), and implies one cannot approximate the top right singular vector v of A by a vector v′ with ‖ v′ – v‖ 2 ≤ ½ with r · s = õ ( n 2 ). 2. For p ∊ {0, 1} and constant α, any sketch must have r · s ≥ n 1−∊ dimensions, for arbitrarily small constant ∊ > 0. 3. For even integers p ≥ 2, we give a sketch with r · s = O ( n 2–4/ p ∊ −2 ) dimensions for obtaining a (1 + ∊)-approximation. This is optimal up to logarithmic factors, and is the first general subquadratic upper bound for sketching the Schatten norms. For general linear sketches our results, though not optimal, are qualitatively similar, showing that for p = ∞, k = Ω( n 3/2 / α 4 ) and for. These give separations in the sketching complexity of Schatten- p norms with the corresponding vector p -norms, and rule out a table lookup nearest-neighbor search for p = 1, making progress on a question of Andoni.

STOC Conference 2014 Conference Paper

Turnstile streaming algorithms might as well be linear sketches

Yi Li 0002
Huy L. Nguyen 0001
David P. Woodruff

In the turnstile model of data streams, an underlying vector x ∈ {-- m ,-- m +1,..., m --1, m } n is presented as a long sequence of positive and negative integer updates to its coordinates. A randomized algorithm seeks to approximate a function f ( x ) with constant probability while only making a single pass over this sequence of updates and using a small amount of space. All known algorithms in this model are linear sketches: they sample a matrix A from a distribution on integer matrices in the preprocessing phase, and maintain the linear sketch A · x while processing the stream. At the end of the stream, they output an arbitrary function of A · x . One cannot help but ask: are linear sketches universal? In this work we answer this question by showing that any 1-pass constant probability streaming algorithm for approximating an arbitrary function f of x in the turnstile model can also be implemented by sampling a matrix A from the uniform distribution on O ( n log m ) integer matrices, with entries of magnitude poly( n ), and maintaining the linear sketch Ax . Furthermore, the logarithm of the number of possible states of Ax , as x ranges over {-- m ,-- m + 1,..., m } n , plus the amount of randomness needed to store A , is at most a logarithmic factor larger than the space required of the space-optimal algorithm. Our result shows that to prove space lower bounds for 1-pass streaming algorithms, it suffices to prove lower bounds in the simultaneous model of communication complexity, rather than the stronger 1-way model. Moreover, the fact that we can assume we have a linear sketch with polynomially-bounded entries further simplifies existing lower bounds, e.g., for frequency moments we present a simpler proof of the Ω( n 1-2/ k ) bit complexity lower bound without using communication complexity.

STOC Conference 2010 Conference Paper

Approximate sparse recovery: optimizing time and measurements

Anna C. Gilbert
Yi Li 0002
Ely Porat
Martin J. Strauss

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 - x k || 2 , where x k 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.