We present initial results from the first empirical evaluation of a graph partitioning algorithm inspired by the Arora-Rao-Vazirani algorithm of [5], which combines spectral and flow methods in a novel way. We have studied the parameter space of this ...

We consider the problem of selecting the "best" subset of exactly k columns from an m x n matrix A. In particular, we present and analyze a novel two-stage algorithm that runs in O(min{mn², m²n}) ...

We provide a report for the ACM SIGKDD community about the 2008 Workshop on Algorithms for Modern Massive Data Sets (MMDS 2008), its origin in MMDS 2006, and future directions for this interdisciplinary research area.

Motivated by numerous applications in which the data may be modeled by a variable subscripted by three or more indices, we develop a tensor-based extension of the matrix CUR decomposition. The tensor-CUR decomposition is most relevant as a data analysis ...

Keywords: CUR decomposition, hyperspectral imagery, recommendation system, tensor decomposition

Principal Components Analysis (PCA) is the predominant linear dimensionality reduction technique, and has been widely applied on datasets in all scientific domains. We consider, both theoretically and empirically, the topic of unsupervised feature selection ...

Keywords: PCA, random sampling, subset selection

Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of “components.” Typically, these components are linear combinations of the rows and columns of the matrix, and are thus difficult ...

Keywords: $CUR$ matrix decomposition, approximate least squares, data analysis, random sampling algorithms

Recent work in the analysis of randomized approximation algorithms for NP-hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed ...

Keywords: CUR matrix decomposition, Max-Cut algorithm, Sampling Linear Programs

A large body of work has been devoted to identifying community structure in networks. A community is often though of as a set of nodes that has more connections between its members than to the remainder of the network. In this paper, we characterize ...

Keywords: community structure, conductance, graph partitioning, random walks, social networks

The ℓ_p regression problem takes as input a matrix A ∈ ℝⁿ, a vector b ∈ ℝⁿ, and a number p ∈ [1, ∞), and it returns as output a number ...

We consider feature selection for text classification both theoretically and empirically. Our main result is an unsupervised feature selection strategy for which we give worst-case theoretical guarantees on the generalization power of the resultant classification ...

Keywords: feature selection, random sampling, regularized least squares classification, text classification