Arrow Research search

Author name cluster

Kenneth L. Clarkson

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.

30 papers
2 author rows

Possible papers

30

ICLR Conference 2024 Conference Paper

Topological data analysis on noisy quantum computers

  • Ismail Yunus Akhalwaya
  • Shashanka Ubaru
  • Kenneth L. Clarkson
  • Mark S. Squillante
  • Vishnu Jejjala
  • Yang-Hui He
  • Kugendran Naidoo
  • Vasileios Kalantzis

Topological data analysis (TDA) is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical algorithms for computing TDA are exorbitant, and quickly become impractical for high-order characteristics. Quantum computers offer the potential of achieving significant speedup for certain computational problems. Indeed, TDA has been purported to be one such problem, yet, quantum computing algorithms proposed for the problem, such as the original Quantum TDA (QTDA) formulation by Lloyd, Garnerone and Zanardi, require fault-tolerance qualifications that are currently unavailable. In this study, we present NISQ-TDA, a fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to high-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm neither suffers from the data-loading problem nor does it need to store the input data on the quantum computer explicitly. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise.

Details

STOC Conference 2022 Conference Paper

Low-rank approximation with 1/ε 1/3 matrix-vector products

  • Ainesh Bakshi
  • Kenneth L. Clarkson
  • David P. Woodruff

We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten- p norm. Here, given access to a matrix A through matrix-vector products, an accuracy parameter є, and a target rank k , the goal is to find a rank- k matrix Z with orthonormal columns such that || A ( I − Z Z ⊤ ) || S p ≤ (1+є)min U ⊤ U = I k || A ( I − U U ⊤ ) || S p , where || M || S p denotes the ℓ p norm of the the singular values of M . For the special cases of p =2 (Frobenius norm) and p = ∞ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses Õ( k /√є) matrix-vector products, improving on the naïve Õ( k /є) dependence obtainable by the power method, where Õ(·) suppresses poly(log( dk /є)) factors.

Details

SODA Conference 2022 Conference Paper

Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time

  • Nadiia Chepurko
  • Kenneth L. Clarkson
  • Praneeth Kacham
  • David P. Woodruff

In the numerical linear algebra community, it was suggested that to obtain nearly optimal bounds for various problems such as rank computation, finding a maximal linearly independent subset of columns (a basis ), regression, or low-rank approximation, a natural way would be to resolve the main open question of Nelson and Nguyen (FOCS, 2013). This question is regarding the logarithmic factors in the sketching dimension of existing oblivious subspace embeddings that achieve constant-factor approximation. We show how to bypass this question using a refined sketching technique, and obtain optimal or nearly optimal bounds for these problems. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors, which after first applying known oblivious subspace embeddings, allows us to quickly spread out the mass of the vector so that sampling is now effective. We thereby avoid a logarithmic factor in the sketching dimension that is standard in bounds proven using the matrix Chernoff inequality. For the fundamental problems of rank computation and finding a basis, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013), and are optimal to within a constant factor and a poly(log log( n ))-factor, respectively. Further, for constant-factor regression and low-rank approximation we give the first optimal algorithms, for the current matrix multiplication exponent.

Details

ICML Conference 2022 Conference Paper

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

  • Nadiia Chepurko
  • Kenneth L. Clarkson
  • Lior Horesh
  • Honghao Lin
  • David P. Woodruff

We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise; these are powerful and standard techniques in randomized numerical linear algebra. With this recognition, we are able to employ the large body of work in numerical linear algebra to obtain algorithms for these problems that are simpler or faster (or both) than existing approaches. Our experiments demonstrate that the proposed data structures also work well on real-world datasets.

Details

ICML Conference 2021 Conference Paper

Projection techniques to update the truncated SVD of evolving matrices with applications

  • Vasileios Kalantzis
  • Georgios Kollias
  • Shashanka Ubaru
  • Athanasios N. Nikolakopoulos
  • Lior Horesh
  • Kenneth L. Clarkson

This submission considers the problem of updating the rank-$k$ truncated Singular Value Decomposition (SVD) of matrices subject to the addition of new rows and/or columns over time. Such matrix problems represent an important computational kernel in applications such as Latent Semantic Indexing and Recommender Systems. Nonetheless, the proposed framework is purely algebraic and targets general updating problems. The algorithm presented in this paper undertakes a projection viewpoint and focuses on building a pair of subspaces which approximate the linear span of the sought singular vectors of the updated matrix. We discuss and analyze two different choices to form the projection subspaces. Results on matrices from real applications suggest that the proposed algorithm can lead to higher accuracy, especially for the singular triplets associated with the largest modulus singular values. Several practical details and key differences with other approaches are also discussed.

Details

ICML Conference 2019 Conference Paper

Dimensionality Reduction for Tukey Regression

  • Kenneth L. Clarkson
  • Ruosong Wang
  • David P. Woodruff

We give the first dimensionality reduction methods for the overconstrained Tukey regression problem. The Tukey loss function $\|y\|_M = \sum_i M(y_i)$ has $M(y_i) \approx |y_i|^p$ for residual errors $y_i$ smaller than a prescribed threshold $\tau$, but $M(y_i)$ becomes constant for errors $|y_i| > \tau$. Our results depend on a new structural result, proven constructively, showing that for any $d$-dimensional subspace $L \subset \mathbb{R}^n$, there is a fixed bounded-size subset of coordinates containing, for every $y \in L$, all the large coordinates, with respect to the Tukey loss function, of $y$. Our methods reduce a given Tukey regression problem to a smaller weighted version, whose solution is a provably good approximate solution to the original problem. Our reductions are fast, simple and easy to implement, and we give empirical results demonstrating their practicality, using existing heuristic solvers for the small versions. We also give exponential-time algorithms giving provably good solutions, and hardness results suggesting that a significant speedup in the worst case is unlikely.

Details

SODA Conference 2017 Conference Paper

Low-Rank PSD Approximation in Input-Sparsity Time

  • Kenneth L. Clarkson
  • David P. Woodruff

We give algorithms for approximation by low-rank positive semidefinite (PSD) matrices. For symmetric input matrix A ∊ ℝ n×n, target rank k, and error parameter ∊ > 0, one algorithm finds with constant probability a PSD matrix Ỹ of rank k suchthat where A k, + denotes the best rank- k PSD approximation to A, and the norm is Frobenius. The algorithm takes time O ( n nz( A ) log n ) + n poly((log n )k/∊) + poly( k /∊), where nnz( A ) denotes the number of nonzero entries of A, and poly( k /∊) denotes a polynomial in k/∊. (There are two different polynomials in the time bound.) Here the output matrix Y has the form CUC T, where the O ( k /∊) columns of c are columns of A. In contrast to prior work, we do not require the input matrix A to be PSD, our output is rank k (not larger), and our running time is O ( n nz ( A ) log n ) provided this is larger than npoly((log n )k/e). We give a similar algorithm that is faster and simpler, but whose rank- k PSD output does not involve columns of A, and does not require A to be symmetric. We give similar algorithms for best rank- k approximation subject to the constraint of symmetry. We also show that there are asymmetric input matrices that cannot have good symmetric column-selected approximations.

Details

FOCS Conference 2015 Conference Paper

Input Sparsity and Hardness for Robust Subspace Approximation

  • Kenneth L. Clarkson
  • David P. Woodruff

In the subspace approximation problem, we seek a k-dimensional subspace F of R d that minimizes the sum of p-th powers of Euclidean distances to a given set of n points a 1, ⋯, a n ∈ R d, for p ≥ 1. More generally than minimizing Σ i dist(a i F) p, we may wish to minimize Σ i M(dist(a i, F)) for some loss function M(), for example, M-Estimators, which include the Huber and Tukey loss functions. Such subspaces provide alternatives to the singular value decomposition (SVD), which is the p = 2 case, finding such an F that minimizes the sum of squares of distances. For p E [1, 2), and for typical M-Estimators, the minimizing F gives a solution that is more robust to outliers than that provided by the SVD. We give several algorithmic results for these robust subspace approximation problems. We state our results as follows, thinking of the n points as forming an n × d matrix A, and letting nnz(A) denote the number of non-zero entries of A. Our results hold for p ∈ [1, 2). We use poly(n) to denote n O(1) as n → ∞. 1) For minimizing Σ i dist(a i, F) p, we give an algorithm running in O(nnz(A) + (n + d)poly(k/ε) + exp(poly(k/ε))) 2) We show that the problem of minimizing Σ i dist(a i, F) p is NP-hard, even to output a (1 + 1/poly(d))-approximation. This extends work of Deshpande et al. (SODA, 2011) which could only show NP-hardness or UGC-hardness for p > 2; their proofs critically rely on p > 2. Our work resolves an open question of [Kannan Vempala, NOW, 2009]. Thus, there cannot be an algorithm running in time polynomial in k and 1/ε unless P = NP. Together with prior work, this implies that the problem is NP-hard for all p ≠ 2. 3) For loss functions for a wide class of M-Estimators, we give a problem-size reduction: for a parameter K = (log n)O(log k), our reduction takes O(nnz(A) logn + (n + d)poly(K/ε)) time to reduce the problem to a constrained version involving matrices whose dimensions are poly(Kε -1 log n). We also give bicriteria solutions. 4) Our techniques lead to the first O(mmz(A) + poly(d/ε)) time algorithms for (1 + ε)-approximate regression for a wide class of convex M-Estimators. This improves prior results [1], which were (1 + ε)-approximation for Huber regression only, and O(1)-approximation for a general class of M-Estimators.

Details

SODA Conference 2015 Conference Paper

Sketching for M -Estimators: A Unified Approach to Robust Regression

  • Kenneth L. Clarkson
  • David P. Woodruff

We give algorithms for the M-estimators min x ‖ Ax — b‖ G, where A ∊ ℝ n × d and b ∊ ℝ n, and ‖ y‖ G for y ∊ ℝ n is specified by a cost function G: ℝ → ℝ ≥0, with ‖ y‖ G ≡ ∑ i G ( y i ). The M -estimators generalize ℓ p regression, for which G ( x ) = We first show that the Huber measure can be computed up to relative error ε in O (nnz( A )log n + poly( d (log n )/ε)) time, where nnz( A ) denotes the number of non-zero entries of the matrix A. Huber is arguably the most widely used M -estimator, enjoying the robustness properties of ℓ 1 as well as the smoothness properties of ℓ 2. We next develop algorithms for general M -estimators. We analyze the M-sketch, which is a variation of a sketch introduced by Verbin and Zhang in the context of estimating the earthmover distance. We show that the M -sketch can be used much more generally for sketching any M- estimator provided G has growth that is at least linear and at most quadratic. Using the M -sketch we solve the M -estimation problem in O (nnz( A ) + poly( d log n )) time for any such G that is convex, making a single pass over the matrix and finding a solution whose residual error is within a constant factor of optimal, with high probability.

Details

STOC Conference 2013 Conference Paper

Low rank approximation and regression in input sparsity time

  • Kenneth L. Clarkson
  • David P. Woodruff

We design a new distribution over poly(r ε -1 ) x n matrices S so that for any fixed n x d matrix A of rank r, with probability at least 9/10, SAx 2 = (1 pm ε)Ax 2 simultaneously for all x ∈ R d . Such a matrix S is called a subspace embedding . Furthermore, SA can be computed in O(nnz(A)) + ~O(r 2 ε -2 ) time, where nnz(A) is the number of non-zero entries of A. This improves over all previous subspace embeddings, which required at least Ω(nd log d) time to achieve this property. We call our matrices S sparse embedding matrices .

Details

SODA Conference 2013 Conference Paper

The Fast Cauchy Transform and Faster Robust Linear Regression

  • Kenneth L. Clarkson
  • Petros Drineas
  • Malik Magdon-Ismail
  • Michael W. Mahoney
  • Xiangrui Meng
  • David P. Woodruff

We provide fast algorithms for overconstrained ℓ p regression and related problems: for an n × d input matrix A and vector b ∊ ℝ n, in O ( nd log n ) time we reduce the problem min x ∊ ℝ d ‖ A x − b ‖ p to the same problem with input matrix A of dimension s × d and corresponding b of dimension s × 1. Here, Ã and are a coreset for the problem, consisting of sampled and rescaled rows of A and b; and s is independent of n and polynomial in d. Our results improve on the best previous algorithms when n ≫ d, for all p ∊ [1, ∞) except p = 2; in particular, they improve the O ( nd 1. 376+ ) running time of Sohler and Woodruff (STOC, 2011) for p = 1, that uses asymptotically fast matrix multiplication, and the O ( nd 5 log n ) time of Dasgupta et al. (SICOMP, 2009) for general p, that uses ellipsoidal rounding. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general ℓ p problems. To complement this theory, we provide a detailed empirical evaluation of implementations of our algorithms for p = 1, comparing them with several related algorithms. Among other things, our empirical results clearly show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for ℓ p spaces and, for p = 1, a fast subspace embedding of independent interest that we call the Fast Cauchy Transform: a matrix Π: ℝ n → ℝ O ( d log d ), found obliviously to A, that approximately preserves the ℓ 1 norms: that is, ‖ Ax ‖ 1 ≈ ‖Π A x ‖ 1, for all x, with distortion O ( d 2 + η log d ), for an arbitrarily small constant η > 0; and, moreover, ΠA can be computed in O ( nd log d ) time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.

Details

SODA Conference 2010 Conference Paper

Self-improving Algorithms for Convex Hulls

  • Kenneth L. Clarkson
  • Wolfgang Mulzer
  • C. Seshadhri 0001

We describe an algorithm for computing planar convex hulls in the self-improving model: given a sequence I 1, I 2, … of planar n -point sets, the upper convex hull conv( I ) of each set I is desired. We assume that there exists a probability distribution D on n -point sets, such that the inputs I j are drawn independently according to D. Furthermore, D is such that the individual points are distributed independently of each other. In other words, the i 'th point is distributed according to D i. The D i 's can be arbitrary but are independent of each other. The distribution D is not known to the algorithm in advance. After a learning phase of n ε rounds, the expected time to compute conv( I ) is O ( n + H (conv( I ))). Here, H (conv( I )) is the entropy of the output, which is a lower bound for the expected running time of any algebraic computation tree that computes the convex hull. (More precisely, H (conv( I )) is the minimum entropy of any random variable that maps I to a description of conv( I ) and to a labeling scheme that proves nonextremality for every point in I not on the hull.) Our algorithm is thus asymptotically optimal for D. (An erratum has been attached to the previously published proceedings.)

Details

FOCS Conference 2010 Conference Paper

Sublinear Optimization for Machine Learning

  • Kenneth L. Clarkson
  • Elad Hazan
  • David P. Woodruff

We give sub linear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and L 2 -SVM, for which sub linear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. We give lower bounds which show the running times of many of our algorithms to be nearly best possible in the unit-cost RAM model. We also give implementations of our algorithms in the semi-streaming setting, obtaining the first low pass polylogarithmic space and sub linear time algorithms achieving arbitrary approximation factor.

Details

STOC Conference 2006 Conference Paper

Building triangulations using epsilon-nets

  • Kenneth L. Clarkson

This work addresses the problem of approximating a manifold by a simplicial mesh, and the related problem of building triangulations for the purpose of piecewise-linear approximation of functions. It has long been understood that the vertices of such meshes or triangulations should be "well-distributed," or satisfy certain "sampling conditions." This work clarifies and extends some algorithms for finding such well-distributed vertices, by showing that they can be regarded as finding ε-nets or Delone sets in appropriate metric spaces. In some cases where such Delone properties were already understood, such as for meshes to approximate smooth manifolds that bound convex bodies, the upper and lower bound results are extended to more general manifolds; in particular, under some general conditions, the minimum Hausdorff distance for a mesh with n simplices to a d-manifold M is Θ((∫ M√|κ(x)|/n) 2/d ) as n ⋺ ∞, where κ(x) is the Gaussian curvature at point x ∈ M. We also relate these constructions to Dudley's approximation scheme for convex bodies, which can be interpreted as involving an ε-net in a metric space whose distance function depends on surface normals.

Details

FOCS Conference 1994 Conference Paper

More Output-Sensitive Geometric Algorithms (Extended Abstract)

  • Kenneth L. Clarkson

A simple idea for speeding up the computation of extrema of a partially ordered set turns out to have a number of interesting applications in geometric algorithms; the resulting algorithms generally replace an appearance of the input size n in the running time by an output size A/spl les/n. In particular, the A coordinate-wise minima of a set of n points in R/sup d/ can be found by an algorithm needing O(nA) time. Given n points uniformly distributed in the unit square, the algorithm needs n+O(n/sup 5/8/) point comparisons on average. Given a set of n points in R/sup d/, another algorithm can find its A extreme points in O(nA) time. Thinning for nearest-neighbor classification can be done in time O(n log n)/spl Sigma//sub i/ A/sub i/n/sub i/, finding the A/sub i/ irredundant points among n/sub i/ points for each class i, where n=/spl Sigma//sub i/ n/sub i/ is the total number of input points. This sharpens a more obvious O(n/sup 3/) algorithm, which is also given here. Another algorithm is given that needs O(n) space to compute the convex hull of n points in O(nA) time. Finally, a new randomized algorithm finds the convex hull of n points in O(n log A) expected time, under the condition that a random subset of the points of size r has expected hull complexity O(r). All but the last of these algorithms has polynomial dependence on the dimension d, except possibly for linear programming. >

Details

FOCS Conference 1992 Conference Paper

Safe and Effective Determinant Evaluation

  • Kenneth L. Clarkson

The problem of evaluating the sign of the determinant of a small matrix aries in many geometric algorithms. Given an n*n matrix A with integer entries, whose columns are all smaller than M in Euclidean norm, the algorithm given evaluates the sign of the determinant det A exactly. The algorithm requires an arithmetic precision of less than 1. 5n+2lgM bits. The number of arithmetic operations needed is O(n/sup 3/)+O(n/sup 2/) log OD(A)/ beta, where OD(A) mod det A mod is the product of the lengths of the columns of A, and beta is the number of 'extra' bits of precision, min(lg(1/u)-1. 1n-2lgn-2, lgN-lgM-1. 5n-1), where u is the roundoff error in approximate arithmetic, and N is the largest representable integer. Since OD(A) >

Details

FOCS Conference 1988 Conference Paper

A Las Vegas Algorithm for Linear Programming When the Dimension Is Small

  • Kenneth L. Clarkson

An algorithm for solving linear programming problems is given. The expected number of arithmetic operations required by the algorithm is given. The expectation is with respect to the random choices made by the algorithm, and the bound holds for any given input. The technique can be extended to other convex programming problems. >

Details

FOCS Conference 1988 Conference Paper

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces

  • Kenneth L. Clarkson
  • Herbert Edelsbrunner
  • Leonidas J. Guibas
  • Micha Sharir
  • Emo Welzl

The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest. >

Details

TCS Journal 1987 Journal Article

Solving related two- and three-dimensional linear programming problems in logarithmic time

  • Leo J. Guibas
  • Jorge Stolfi
  • Kenneth L. Clarkson

Given n linear inequalities in three variables, we show how to construct a corresponding spherical subdivision using great circle arcs in time O(n log n) and space O(n). This subdivision in turn allows us to compute the point in space satisfying all inequalities and maximizing any desired linear objective function in time O(log n).

Details DOI
v2026.09.13