One-pass additive-error subset selection for $\ell_{p}$ subspace approximation

• URL: http://arxiv.org/abs/2204.12073v1
• Date: Tue, 26 Apr 2022 04:51:36 GMT
• Title: One-pass additive-error subset selection for $\ell_{p}$ subspace approximation
• Authors: Amit Deshpande and Rameshwar Pratap
• Abstract summary: We consider the problem of subset selection for $ell_p$ subspace approximation. We give a one-pass subset selection with an additive approximation guarantee for $ell_p$ subspace approximation.
• Score: 6.186553186139257
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of subset selection for $\ell_{p}$ subspace approximation, that is, to efficiently find a \emph{small} subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. Previously known subset selection algorithms based on volume sampling and adaptive sampling \cite{DeshpandeV07}, for the general case of $p \in [1, \infty)$, require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for $\ell_{p}$ subspace approximation, for any $p \in [1, \infty)$. Earlier subset selection algorithms that give a one-pass multiplicative $(1+\epsilon)$ approximation work under the special cases. Cohen \textit{et al.} \cite{CohenMM17} gives a one-pass subset section that offers multiplicative $(1+\epsilon)$ approximation guarantee for the special case of $\ell_{2}$ subspace approximation. Mahabadi \textit{et al.} \cite{MahabadiRWZ20} gives a one-pass \emph{noisy} subset selection with $(1+\epsilon)$ approximation guarantee for $\ell_{p}$ subspace approximation when $p \in \{1, 2\}$. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any $p \in [1, \infty)$.

Related papers

• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation. We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
  A popular approach to cope with the NP-hardness of the $ell_p$ subspace approximation problem is to compute a strong coreset. We obtain the first algorithm for constructing a strong coreset for $ell_p$ subspace approximation with a nearly optimal dependence on the rank parameter $k$. Our techniques also lead to the first nearly optimal online strong coresets for $ell_p$ subspace approximation with similar bounds as the offline setting.
  arXiv  Detail & Related papers  (2024-07-03T16:49:28Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  The paper revisits step-size selection in a general Markovian setting. A major conclusion is that the choice of $rho =0$ or even $rho1/2$ is justified only in select settings.
  arXiv  Detail & Related papers  (2024-05-28T05:11:05Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  We bridge the gap between the exponents of $n$ in the upper and lower bounds on the additive error with two new algorithms. It is possible to solve the locally private $k$-means problem in a constant number of rounds with constant factor multiplicative approximation.
  arXiv  Detail & Related papers  (2021-05-31T14:41:40Z)
• On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling [3.1822873305165618]
  Sampling-based subset selection techniques require adaptive sampling iterations with multiple passes over the data. We propose an MCMC algorithm to reduce the number of passes required by previous subset selection algorithms. Our algorithm picks a subset of size $mathrmpoly(k/epsilon)$ that gives $(1+epsilon)$ approximation to the optimal subspace.
  arXiv  Detail & Related papers  (2021-03-20T06:07:30Z)
• Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation [0.0]
  We give the first time column subset selection-based $ell_p$ low rank approximation algorithm sampling $tildeO(k)$ columns. We extend our results to obtain tight upper and lower bounds for column subset selection-based $ell_p$ low rank approximation for any $1 p 2$.
  arXiv  Detail & Related papers  (2020-07-20T17:50:30Z)
• Subspace approximation with outliers [6.186553186139257]
  We show how to extend dimension reduction techniques and bi-criteria approximations based on sampling to the problem of subspace approximation with outliers. Our results hold even when the fraction of outliers $alpha$ is large, as long as the obvious condition $0 delta leq 1 - alpha$ is satisfied.
  arXiv  Detail & Related papers  (2020-06-30T07:22:33Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.