Library

High-Dimensional Geometric Streaming for Nearly Low Rank Data

We study streaming algorithms for the $\ell_p$ subspace approximation problem. Given points $a_1, \ldots, a_n$ as an insertion-only stream and a rank parameter $k$, the $\ell_p$ subspace approximation problem is to find a $k$-dimensional subspace $V$ such that $(\sum_{i=1}^n d(a_i, V)^p)^{1/p}$ is minimized, where $d(a, V)$ denotes the Euclidean distance between $a$ and $V$ defined as $\min_{v \in V}\|{a - v}\|_{\infty}$. When $p = \infty$, we need to find a subspace $V$ that minimizes $\max_i d(a_i, V)$. For $\ell_{\infty}$ subspace approximation, we give a deterministic strong coreset construction algorithm and show that it can be used to compute a $\text{poly}(k, \log n)$ approximate solution. We show that the distortion obtained by our coreset is nearly tight for any sublinear space algorithm. For $\ell_p$ subspace approximation, we show that suitably scaling the points and then using our $\ell_{\infty}$ coreset construction, we can compute a $\text{poly}(k, \log n)$ approximation. Our algorithms are easy to implement and run very fast on large datasets. We also use our strong coreset construction to improve the results in a recent work of Woodruff and Yasuda (FOCS 2022) which gives streaming algorithms for high-dimensional geometric problems such as width estimation, convex hull estimation, and volume estimation.

Data Stream Mining TechniquesImage and Video Quality AssessmentData Management and AlgorithmsComputer ScienceMathematics
Source

Paper

Similar papers

Clustering High Dimensional Dynamic Data StreamsV. Braverman, Gereon Frahling, Harry Lang et al.2017 · International Conference on Machine Learning · 55 citations In Library
Efficient Streaming Algorithms for Two-Dimensional Congruence Testing and Geometric HashingYen‐Cheng Chang, Tsun Ming Cheung, Meng-Tsung Tsai et al.2026 · Open MIND In Library
Coresets for constrained k-median and k-means clustering in low dimensional Euclidean spaceMelanie Schmidt, Julian Wargalla2021 · arXiv.org · 3 citations In Library
k-Means for Streaming and Distributed Big Sparse DataArtem Barger, Dan Feldman2015 · SDM · 32 citations In Library
Tensor-Based Sketching Method for the Low-Rank Approximation of Data StreamsCuiyu Liu, Chuanfu Xiao, Mingshuo Ding et al.2022 · International Conference on Learning Representations · 4 citations In Library
Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCAChun-Liang Li, Hsuan-Tien Lin, Chi-Jen Lu2015 · International Conference on Artificial Intelligence and Statistics · 29 citations In Library
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic StreamsSanjeev Khanna, Ashwin Padaki, Krish Singal et al.2025 · arXiv (Cornell University) In Library
Do Less, Get More: Streaming Submodular Maximization with SubsamplingMoran Feldman, Amin Karbasi, Ehsan Kazemi2018 · Neural Information Processing Systems · 96 citations In Library
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile StreamingGregory Dexter, P. Drineas, David P. Woodruff et al.2023 · Neural Information Processing Systems · 0 citations In Library
Streaming Algorithms for High-Dimensional Robust StatisticsIlias Diakonikolas, D. Kane, Ankit Pensia et al.2022 · International Conference on Machine Learning · 26 citations In Library

Peer review

RejectICLR 2024 · via OpenReview
Reviewer YvdX6/10 · confidence 3/52023-10-31

Summary

This paper studies the outer (d - k)-radius estimation problem. This problem may be viewed as a clustering problem, where the goal is to find a k-flat F, such that the max distance of every data point to F is minimized. This is a generalization of the 1-center clustering, where k = 0. This paper gives a (strong) coreset for the problem with approximation ratio poly(k log n) and size poly(k logn). Here, A subset of points S is an \alpha-coreset, if for every k-flat F, the objective evaluated on S is in between [OPT, \alpha OPT]. This eventually implies a streaming algorithm that can achieve the same (order) of ratio. Other extensions are also considered, and various similar results are obtained. Specifically, the main bound can be improved a little bit (in terms of the dependent in k and log n), by assuming a bounded rank-k condition number. Another extension is to consider an \ell_p aggregation function, which means the objective is changed to the sum of p-th power of distance of a data point to F. For this setting, a similar streaming bound can be obtained, but with a weaker error bound.

Strengths

- The study is well-motivated. In particular, the problem is related to clustering and subspace approximation which are fundamental ML/data analysis tasks, and the streaming setting addresses the computational issues of ML in the big data era. - The result can also be applied to improve a recent paper [17] in a certain case, which is a nice application that shows the theoretical relevance of the paper - The paper also provides experiments, which indicate that the seemingly complicated steps can actually be implemented and have the potential to be used in practice

Weaknesses

- The paper is quite technical and is not easy to understand especially for general audience. In addition, too many results are squeezed into the 9 pages. In my point of view, the author could focus on the main result Theorem 1.1, and this itself should already fit the volume of an ICLR paper (considering the 9 pages of the main text). - I don't see a related work section. Since your main technique is coreset, it might make sense to mention works related to coreset. - In fact, the discussion of the coreset literature is almost completely missing. Since your problem may be viewed as 1-center projective clustering, it's important to compare it with the relevant coreset literature. For example, this paper seems relevant: "New Coresets for Projective Clustering and Applications. Tukan et al. AISTATS 2022". From what I read, they gave O(1)-error coreset, but the size is k^k. - It is not discussed if the coreset is tight or can be improved, in terms of the error bound

Questions

- Does JL work here? In particular, can one reduce d to O(log n)? Or maybe subspace JL that reduce to O(k) dimension? I didn't find this discussed/mentioned. This is important as I guess otherwise your approach may not improve WS22? It may be useful to have a brief discussion of this in the paper. - It seems Theorem 3.3 and Theorem 3.6 are in different models of streaming algorithms? Also, does the streaming algorithm in Theorem 3.3 work if deletions are allowed? Please clarify in the paper. - In both Theorem 3.3 and Theorem 3.6 it is mentioned that the coordiantes are integers. Is this necessary even for the offline algorithm, or it is only a matter of storage model? Please clarify in the paper.

Rating

6: marginally above the acceptance threshold

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Authorsrebuttal2023-11-17

- **Reorganizing the paper**: We will think about better ways to reorganize the paper to make it more understandable to the general audience. We think the applications to width estimation, convex hull approximation are important and should be present in the main paper and we will look for ways to make the presentation a bit less dense. - **Related work**: We will add a discussion about the existing coreset literature in the streaming/non-streaming settings for subspace approximation and related problems. We note that ours is the first strong coreset construction, with only poly(k, log n) points, for $\ell_{\infty}$ subspace approximation in the streaming setting and as we show the strong coreset property is important to obtain our applications. - **Projecting with JL**: It is not clear how to obtain strong coreset properties by projecting to lower dimensions using JL transforms in the streaming setting. Usually, projections with JL are used to obtain approximate sensitivities and then a strong coreset is constructed. But this cannot be implemented in the streaming setting with one pass. Kerber and Raghavendra (CCCG 2015) show that when we project to poly(k, log n) dimensions and construct a coreset, we can preserve the costs and extract a solution but we cannot approximate the cost of every subspace and obtain our application such as width estimation, convex hull etc. - **Streaming Model**: All the results in our paper are in the row-arrival model where we see one point after another. Our results do not hold when points can later be deleted. - **Integer Points**: It is not necessary for the points to have integer coordinates. We use bounded integer assumption to only obtain results that are independent of the condition number of the data. However, the algorithms will work even for arbitrary values and the size of the coreset constructed will depend on a specific condition number of the dataset.

Authorsrebuttal2023-11-21

Reminder

A reminder that the discussion period ends tomorrow. Please ask us if you have any questions about the paper and the rebuttal.

Reviewer TTZL8/10 · confidence 3/52023-11-02

Summary

The contributions of the paper are several-fold and it is indeed a bit hard to describe them succinctly... I will not go over all of them in this summary but give a basic flavor of what the paper does. The paper considers several (somewhat) related problems in high-dimensional geometry and provides streaming algorithms for solving these problems. For some problems, like the "outer $(d-k)$-radius estimation problem", this paper provides the first streaming algorithms which use space that is poly$(k,d, \log (n))$ with a distortion factor also being poly$(k,d, \log (n))$. Here, we are given $n$ points in $\mathbb{R}^d$, along with a parameter $k < d$. Their algorithm works by constructing coresets using **online ridge leverage scores**. For some other problems studied in the paper, prior work by Woodruff and Yasuda [FOCS 2022] already provided the first streaming algorithms using space poly$(d, \log (n))$ with a distortion factor also being poly$(d, \log (n))$. Woodruff and Yasuda also construct coresets but by using **online leverage scores**. In this submission, they show that assuming that the data points all approximately come from a low-rank subspace (which seems reasonable), their coreset algorithm can be used to provide streaming algorithms which are more efficient than the ones proposed by Woodruff and Yasuda.

Strengths

Originality: First paper to provide streaming algorithms for the outer $(d-k)$-radius estimation problem. Their coreset algorithm is new and as they show has several applications. Would be of future interest to researchers working on other related problems. Quality and Clarity: Paper is very well-written, easy to understand. I have not checked all the technical details in the proofs but they are very well-explained and it is unlikely that there are any major issues. Significance: The paper's key contribution is providing a coreset construction algorithm, which they prove works for the problems which they consider, but also can be used independently (although without guarantees) for training other ML models.

Weaknesses

Not any that I can see right now.

Questions

None for now.

Rating

8: accept, good paper

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Reviewer XBn63/10 · confidence 3/52023-11-02

Summary

In this paper, the authors consider the problem of designing a streaming algorithm for the $(d-k)$-dimensional radius approximation, i.e., find a $k$-dimensional flat that minimizes the maximum distance of any input point to this flat. When $k=0$, the problem is the well-known minimum enclosing ball problem, i.e., the smallest d-dimensional ball that encloses all input points. They also consider the $\ell_p$-sapce approximation problem. Overall, there are two major results that the authors claim: 1) A single-pass streaming algorithm for $(d-k)$-radius estimation that has poly$(k,\log n)$ approximation using poly$(k, \log n)$ space. The algorithm maintains a coreset (a small subset of points) that approximates the $(d-k)$-radius in the streaming setting. 2) The authors then extend this algorithm to the $\ell_p$-subspace approximation problem and design a streaming algorithm for this setting. The space requirement and the approximation ratios are poly$(k,\log n)$

Strengths

The authors present a rather simple streaming algorithm for the $\ell_p$-subspace approximation problem and show its practical value via experiments.

Weaknesses

The authors do not present the state-of-the-art for $\ell_\infty$-subspace approximation. For instance, when k is 0 or 1, there are O(1)-approximations (see for instance, Chan and Pathak CGTA 2014, Agarwal and Sharathkumar, (SODA 2010, Algorithmica, 2015) and some other followup work. Although for restricted k, they achieve significantly better approximation ratios. Does your algorithm achieve similar ratios when k is small? These algorithms are equally simple: Does your algorithm have a better empirical performance for instance for the MEB problem? For width approximation, there are no randomized algorithm can achieve better than $d^{1/3}$-approximation while using $e^{d^{1/3}}$ space, this was shown in Agarwal and Sharathkumar, (SODA 2010, Algorithmica 2015). I think it is important to place your result in the context of this lower bound. Overall, I had difficulty in understanding the impact and importance of this work and this, I believe, is mainly due to lack of a good comparison with existing work.

Questions

Apart from the questions/concerns above, can you compare your work with the results in Kerber and Raghvendra (CCCG 2015): https://research.cs.queensu.ca/cccg2015/CCCG15-papers/16.pdf In particular, can one first apply JL-projection to d= O(poly{k, \log n}) dimensional space and then run a standard streaming algorithm for this space that gives O(d) =O(poly{k,\log n})-approximation in O(poly{k,\log n}) space?

Rating

3: reject, not good enough

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Authorsrebuttal2023-11-17

We will recap our main contributions here: - A **deterministic** coreset construction algorithm for $\ell_{\infty}$ subspace approximation with **any** rank parameter k. We are not aware of any previous works with streaming algorithms that work for any given rank parameter k. - A black-box **randomized reduction** from an $\ell_p$ subspace approximation coreset to an $\ell_{\infty}$ subspace approximation coreset for any rank k using scaled exponential random variables. This reduction is also new and may have additional applications since any improvement in an $\ell_{\infty}$ coreset construction would **directly improve** the $\ell_p$ coreset construction as well. - Deterministic Streaming Algorithms for other problems such as convex hull estimation, volume estimation, and width estimation in any direction, for almost low rank data with better guarantees than previous work of Woodruff and Yasuda (FOCS 2022) Our main motivation was to obtain streaming algorithms that work for values of k that are not just small constants as well. This particular problem seems to have not been studied in the streaming setting. We will add references to the line of work studying streaming algorithms for k=0,1 and add a discussion to place our results in context. - For k=0 and 1, we do not expect our algorithms to be better than the algorithms that are specifically constructed for those values of k. For MEB (k=0), our algorithm is essentially exactly the simple 2 approximation algorithm: pick an arbitrary point (in our case we pick the first) and essentially compute the distance of the farthest point from the first point. So, we do not expect to do better than the 2-approximation using our algorithm for k=0. - The width estimation problem, as studied in Agarwal and Sharathkumar (SODA 2014), corresponds to the case of k = d-1 for the $\ell_{\infty}$ subspace approximation problem. The hardness result of Agarwal and Sharathkumar is, as you stated, for approximating to a better factor than d^{1/3} in small space. Our streaming coreset construction gives only multiplicative approximation up to a factor of d^{3/2} in a bounded integer points case and a d^{1/2} factor for well-conditioned instances in this setting (k=d-1) and hence makes a poly(d) space streaming algorithm possible. **Comparison with Project-and-Construct Coreset**: For $\ell_{\infty}$ subspace approximation, ours is a **strong coreset** construction which can be used to approximate the subspace approximation cost of any **k-dimensional subspace**. As we show this strong coreset property has applications to width estimation in arbitrary directions, volume estimation etc. The random projection method in Kerber and Raghvendra (CCCG 2015) only preserves the optimal projective clustering cost up to 1+eps approximation but cannot be used to approximate the projection cost of arbitrary subspaces. For $\ell_p$ subspace approximation though, our coreset construction can also not approximate costs for arbitrary inputs.

Authorsrebuttal2023-11-21

Reminder

A reminder that the discussion period ends tomorrow. Please ask us if you have any questions about our rebuttal.

Area Chair dttimeta-review2023-12-06

Meta-review

The paper proposes a new coreset algorithms for 1-center projective clustering with a wide range of parameters that can be applied to the streaming setting. In this problem, we are given a dataset in d dimensions and we would like to find a small subset (a coreset) such that for any given k-dimensional subspace, the maximum distance between the subspace and the subset is approximately the maximum distance between the subspace and the original data. The new algorithm also works in the streaming setting where we have low memory and can only scan through the dataset once. The paper also extends the result to the case where the clustering cost is an l_p norm of the vector whose entries are the distances as opposed to l_infinity (the maximum). The reviewers all appreciate the importance of the particular clustering problem considered in the paper. They also note that the algorithm can be implemented and give reasonable results in the experiments. On the downside, two reviewers note the lack of comparison with previous works even for special cases to show the significance of the improved guarantee. For example, when k=0 or 1, which are two common settings, the existing algorithms have much stronger guarantees. One reviewer also questions whether the bounds are close to tight, which is related to the previous point because the paper does not connect with previous lower bounds for the same problem.

Why not a higher score

The lack of comparison with the existing literature is concerning as it seems there are a lot of previous works at least for the important special cases and the new work seems to give worse results for a more general setting and not a strict generalization. The positive reviewer suggests that the new algorithm is the first for the problem and can bring additional attention to the task but it seems that there is already significant related literature that was not thoroughly covered by the paper.

Why not a lower score

N/A

© 2026 NYSGPT2525 LLC