Dan Feldman

ICRA Conference 2023 Conference Paper

Deep Learning on Home Drone: Searching for the Optimal Architecture

• Alaa Maalouf
• Yotam Gurfinkel
• Barak Diker
• Oren Gal
• Daniela Rus
• Dan Feldman

We suggest the first system that runs real-time semantic segmentation via deep learning on the weak microcomputer Raspberry Pi Zero v2 (whose price was $15) attached to a toy drone. In particular, since the Raspberry Pi weighs less than 16 grams, and its size is half of a credit card, we could easily attach it to the common commercial DJI Tello toy-drone ( $\times 92. 5\times 41$ mm). The result is an autonomous drone (no laptop nor human in the loop) that can detect and classify objects in real-time from a video stream of an onboard monocular RGB camera (no GPS or LIDAR sensors). The companion videos demonstrate how this Tello drone scans the lab for people (e. g. for the use of firefighters or security forces) and for an empty parking slot outside the lab. Existing deep learning solutions are either much too slow for real-time computation on such IoT devices, or provide results of impractical quality. Our main challenge was to design a system that takes the best of all worlds among numerous combinations of networks, deep learning platforms/frameworks, compression techniques, and compression ratios. To this end, we provide an efficient searching algorithm that aims to find the optimal combination which results in the best tradeoff between the network running time and its accuracy/performance.

ICML Conference 2023 Conference Paper

Provable Data Subset Selection For Efficient Neural Networks Training

• Murad Tukan
• Samson Zhou
• Alaa Maalouf
• Daniela Rus
• Vladimir Braverman
• Dan Feldman

Radial basis function neural networks ( RBFNN ) are well-known for their capability to approximate any continuous function on a closed bounded set with arbitrary precision given enough hidden neurons. In this paper, we introduce the first algorithm to construct coresets for RBFNNs, i. e. , small weighted subsets that approximate the loss of the input data on any radial basis function network and thus approximate any function defined by an RBFNN on the larger input data. In particular, we construct coresets for radial basis and Laplacian loss functions. We then use our coresets to obtain a provable data subset selection algorithm for training deep neural networks. Since our coresets approximate every function, they also approximate the gradient of each weight in a neural network, which is a particular function on the input. We then perform empirical evaluations on function approximation and dataset subset selection on popular network architectures and data sets, demonstrating the efficacy and accuracy of our coreset construction.

NeurIPS Conference 2022 Conference Paper

Coreset for Line-Sets Clustering

• Sagi Lotan
• Ernesto Evgeniy Sanches Shayda
• Dan Feldman

The input to the {line-sets $k$-median} problem is an integer $k \geq 1$, and a set $\mathcal{L} = \{L_1, \dots, L_n\}$that contains $n$ sets of lines in $\mathbb{R}^d$. The goal is to compute a set $C$ of $k$ centers (points in $\mathbb{R}^d$) that minimizes the sum $\sum_{L \in \mathcal{L}}\min_{\ell\in L, c\in C}\mathrm{dist}(\ell, c)$ of Euclidean distances from each set to its closest center, where $\mathrm{dist}(\ell, c): =\min_{x\in \ell}\norm{x-c}_2$. An \emph{$\varepsilon$-coreset} for this problem is a weighted subset of sets in $\mathcal{L}$ that approximates this sum up to $1 \pm \varepsilon$ multiplicative factor, for every set $C$ of $k$ centers. We prove that \emph{every} such input set $\set{L}$ has a small $\varepsilon$-coreset, and provide the first coreset construction for this problem and its variants. The coreset consists of $O(\log^2n)$ weighted line-sets from $\set{L}$, and is constructed in $O(n\log n)$ time for every fixed $d, k\geq 1$ and $\varepsilon \in (0, 1)$. The main technique is based on a novel reduction to a ``fair clustering'' of colored points to colored centers. We then provide a coreset for this coloring problem, which may be of independent interest. Open source code and experiments are also provided.

ICML Conference 2022 Conference Paper

Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more

• Elad Tolochinsky
• Ibrahim Jubran
• Dan Feldman

Coreset (or core-set) is a small weighted subset $Q$ of an input set $P$ with respect to a given monotonic function $f: \mathbb{R}\to\mathbb{R}$ that provably approximates its fitting loss $\sum_{p\in P}f(p\cdot x)$ to any given $x\in\mathbb{R}^d$. Using $Q$ we can obtain an approximation of $x^*$ that minimizes this loss, by running existing optimization algorithms on $Q$. In this work we provide: (i) A lower bound which proves that there are sets with no coresets smaller than $n=|P|$ for general monotonic loss functions. (ii) A proof that, with an additional common regularization term and under a natural assumption that holds e. g. for logistic regression and the sigmoid activation functions, a small coreset exists for any input $P$. (iii) A generic coreset construction algorithm that computes such a small coreset $Q$ in $O(nd+n\log n)$ time, and (iv) Experimental results with open-source code which demonstrate that our coresets are effective and are much smaller in practice than predicted in theory.

IROS Conference 2022 Conference Paper

Newton-PnP: Real-time Visual Navigation for Autonomous Toy-Drones

• Ibrahim Jubran
• Fares Fares
• Yuval Alfassi
• Firas Ayoub
• Dan Feldman

The Perspective-n-Point problem aims to estimate the relative pose between a calibrated monocular camera and a known 3D model, by aligning pairs of 2D captured image points to their corresponding 3D points in the model. We suggest an algorithm that runs on weak IoT devices in real-time but still provides provable theoretical guarantees for both running time and correctness. Existing solvers provide only one of these requirements. Our main motivation was to turn the popular DJI's Tello Drone (<90gr, <$100) into an autonomous drone that navigates in an indoor environment with no external human/laptop/sensor, by simply attaching a Raspberry PI Zero (<9gr, <$25) to it. This tiny micro-processor takes as input a real-time video from a tiny RGB camera, and runs our PnP solver on-board. Extensive experimental results, open source code, and a demonstration video are included.

IROS Conference 2022 Conference Paper

Obstacle Aware Sampling for Path Planning

• Murad Tukan
• Alaa Maalouf
• Dan Feldman
• Roi Poranne

Many path planning algorithms are based on sampling the state space. While this approach is very simple, it can become costly when the obstacles are unknown, since samples hitting these obstacles are wasted. The goal of this paper is to efficiently identify obstacles in a map and remove them from the sampling space. To this end, we propose a pre-processing algorithm for space exploration that enables more efficient sampling. We show that it can boost the performance of other space sampling methods and path planners. Our approach is based on the fact that a convex obstacle can be approximated provably well by its minimum volume enclosing ellipsoid (MVEE), and a non-convex obstacle may be partitioned into convex shapes. Our main contribution is an al-gorithm that strategically finds a small sample, called the active-coreset, that adaptively samples the space via membership-oracle such that the MVEE of the coreset approximates the MVEE of the obstacle. Experimental results confirm the ef-fectiveness of our approach across multiple planners based on rapidly-exploring random trees, showing significant improve-ment in terms of time and path length.

NeurIPS Conference 2021 Conference Paper

Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition

• Lucas Liebenwein
• Alaa Maalouf
• Dan Feldman
• Daniela Rus

We present a novel global compression framework for deep neural networks that automatically analyzes each layer to identify the optimal per-layer compression ratio, while simultaneously achieving the desired overall compression. Our algorithm hinges on the idea of compressing each convolutional (or fully-connected) layer by slicing its channels into multiple groups and decomposing each group via low-rank decomposition. At the core of our algorithm is the derivation of layer-wise error bounds from the Eckart–Young–Mirsky theorem. We then leverage these bounds to frame the compression problem as an optimization problem where we wish to minimize the maximum compression error across layers and propose an efficient algorithm towards a solution. Our experiments indicate that our method outperforms existing low-rank compression approaches across a wide range of networks and data sets. We believe that our results open up new avenues for future research into the global performance-size trade-offs of modern neural networks.

NeurIPS Conference 2021 Conference Paper

Coresets for Decision Trees of Signals

• Ibrahim Jubran
• Ernesto Evgeniy Sanches Shayda
• Ilan I Newman
• Dan Feldman

A $k$-decision tree $t$ (or $k$-tree) is a recursive partition of a matrix (2D-signal) into $k\geq 1$ block matrices (axis-parallel rectangles, leaves) where each rectangle is assigned a real label. Its regression or classification loss to a given matrix $D$ of $N$ entries (labels) is the sum of squared differences over every label in $D$ and its assigned label by $t$. Given an error parameter $\varepsilon\in(0, 1)$, a $(k, \varepsilon)$-coreset $C$ of $D$ is a small summarization that provably approximates this loss to \emph{every} such tree, up to a multiplicative factor of $1\pm\varepsilon$. In particular, the optimal $k$-tree of $C$ is a $(1+\varepsilon)$-approximation to the optimal $k$-tree of $D$. We provide the first algorithm that outputs such a $(k, \varepsilon)$-coreset for \emph{every} such matrix $D$. The size $|C|$ of the coreset is polynomial in $k\log(N)/\varepsilon$, and its construction takes $O(Nk)$ time. This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry. Experimental results on \texttt{sklearn} and \texttt{lightGBM} show that applying our coresets on real-world data-sets boosts the computation time of random forests and their parameter tuning by up to x$10$, while keeping similar accuracy. Full open source code is provided.

ICLR Conference 2021 Conference Paper

Deep Learning meets Projective Clustering

• Alaa Maalouf
• Harry Lang
• Daniela Rus
• Dan Feldman

A common approach for compressing Natural Language Processing (NLP) networks is to encode the embedding layer as a matrix $A\in\mathbb{R}^{n\times d}$, compute its rank-$j$ approximation $A_j$ via SVD (Singular Value Decomposition), and then factor $A_j$ into a pair of matrices that correspond to smaller fully-connected layers to replace the original embedding layer. Geometrically, the rows of $A$ represent points in $\mathbb{R}^d$, and the rows of $A_j$ represent their projections onto the $j$-dimensional subspace that minimizes the sum of squared distances (``errors'') to the points. In practice, these rows of $A$ may be spread around $k>1$ subspaces, so factoring $A$ based on a single subspace may lead to large errors that turn into large drops in accuracy. Inspired by \emph{projective clustering} from computational geometry, we suggest replacing this subspace by a set of $k$ subspaces, each of dimension $j$, that minimizes the sum of squared distances over every point (row in $A$) to its \emph{closest} subspace. Based on this approach, we provide a novel architecture that replaces the original embedding layer by a set of $k$ small layers that operate in parallel and are then recombined with a single fully-connected layer. Extensive experimental results on the GLUE benchmark yield networks that are both more accurate and smaller compared to the standard matrix factorization (SVD). For example, we further compress DistilBERT by reducing the size of the embedding layer by $40\%$ while incurring only a $0.5\%$ average drop in accuracy over all nine GLUE tasks, compared to a $2.8\%$ drop using the existing SVD approach. On RoBERTa we achieve $43\%$ compression of the embedding layer with less than a $0.8\%$ average drop in accuracy as compared to a $3\%$ drop previously.

TCS Journal 2021 Journal Article

On coresets for support vector machines

• Murad Tukan
• Cenk Baykal
• Dan Feldman
• Daniela Rus

NeurIPS Conference 2020 Conference Paper

Coresets for Near-Convex Functions

• Murad Tukan
• Alaa Maalouf
• Dan Feldman

Coreset is usually a small weighted subset of $n$ input points in $\mathbb{R}^d$, that provably approximates their loss function for a given set of queries (models, classifiers, etc. ). Coresets become increasingly common in machine learning since existing heuristics or inefficient algorithms may be improved by running them possibly many times on the small coreset that can be maintained for streaming distributed data. Coresets can be obtained by sensitivity (importance) sampling, where its size is proportional to the total sum of sensitivities. Unfortunately, computing the sensitivity of each point is problem dependent and may be harder to compute than the original optimization problem at hand. We suggest a generic framework for computing sensitivities (and thus coresets) for wide family of loss functions which we call near-convex functions. This is by suggesting the $f$-SVD factorization that generalizes the SVD factorization of matrices to functions. Example applications include coresets that are either new or significantly improves previous results, such as SVM, Logistic regression, M-estimators, and $\ell_z$-regression. Experimental results and open source are also provided.

ICLR Conference 2020 Conference Paper

Data-Independent Neural Pruning via Coresets

• Ben Mussay
• Margarita Osadchy
• Vladimir Braverman
• Samson Zhou
• Dan Feldman

Previous work showed empirically that large neural networks can be significantly reduced in size while preserving their accuracy. Model compression became a central research topic, as it is crucial for deployment of neural networks on devices with limited computational and memory resources. The majority of the compression methods are based on heuristics and offer no worst-case guarantees on the trade-off between the compression rate and the approximation error for an arbitrarily new sample. We propose the first efficient, data-independent neural pruning algorithm with a provable trade-off between its compression rate and the approximation error for any future test sample. Our method is based on the coreset framework, which finds a small weighted subset of points that provably approximates the original inputs. Specifically, we approximate the output of a layer of neurons by a coreset of neurons in the previous layer and discard the rest. We apply this framework in a layer-by-layer fashion from the top to the bottom. Unlike previous works, our coreset is data independent, meaning that it provably guarantees the accuracy of the function for any input $x\in \mathbb{R}^d$, including an adversarial one. We demonstrate the effectiveness of our method on popular network architectures. In particular, our coresets yield 90% compression of the LeNet-300-100 architecture on MNIST while improving the accuracy.

ICLR Conference 2020 Conference Paper

Provable Filter Pruning for Efficient Neural Networks

• Lucas Liebenwein
• Cenk Baykal
• Harry Lang
• Dan Feldman
• Daniela Rus

We present a provable, sampling-based approach for generating compact Convolutional Neural Networks (CNNs) by identifying and removing redundant filters from an over-parameterized network. Our algorithm uses a small batch of input data points to assign a saliency score to each filter and constructs an importance sampling distribution where filters that highly affect the output are sampled with correspondingly high probability. In contrast to existing filter pruning approaches, our method is simultaneously data-informed, exhibits provable guarantees on the size and performance of the pruned network, and is widely applicable to varying network architectures and data sets. Our analytical bounds bridge the notions of compressibility and importance of network structures, which gives rise to a fully-automated procedure for identifying and preserving filters in layers that are essential to the network's performance. Our experimental evaluations on popular architectures and data sets show that our algorithm consistently generates sparser and more efficient models than those constructed by existing filter pruning approaches.

EAAI Journal 2020 Journal Article

Real-time EEG classification via coresets for BCI applications

• Eitan Netzer
• Alex Frid
• Dan Feldman

ICML Conference 2020 Conference Paper

Sets Clustering

• Ibrahim Jubran
• Murad Tukan
• Alaa Maalouf
• Dan Feldman

The input to the \emph{sets-$k$-means} problem is an integer $k\geq 1$ and a set $\mathcal{P}=\{P_1, \cdots, P_n\}$ of fixed sized sets in $\mathbb{R}^d$. The goal is to compute a set $C$ of $k$ centers (points) in $\mathbb{R}^d$ that minimizes the sum $\sum_{P\in \mathcal{P}} \min_{p\in P, c\in C}\left\|{p}-c \right\|^2$ of squared distances to these sets. An \emph{$\varepsilon$-core-set} for this problem is a weighted subset of $\mathcal{P}$ that approximates this sum up to $1\pm\varepsilon$ factor, for \emph{every} set $C$ of $k$ centers in $\mathbb{R}^d$. We prove that such a core-set of $O(\log^2{n})$ sets always exists, and can be computed in $O(n\log{n})$ time, for every input $\mathcal{P}$ and every fixed $d, k\geq 1$ and $\varepsilon \in (0, 1)$. The result easily generalized for any metric space, distances to the power of $z>0$, and M-estimators that handle outliers. Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS ($1+\varepsilon$ approximation) for the sets-$k$-means problem that takes time near linear in $n$. This is the first result even for sets-mean on the plane ($k=1$, $d=2$). Open source code and experimental results for document classification and facility locations are also provided.

NeurIPS Conference 2019 Conference Paper

Fast and Accurate Least-Mean-Squares Solvers

• Alaa Maalouf
• Ibrahim Jubran
• Dan Feldman

Least-mean squares (LMS) solvers such as Linear / Ridge / Lasso-Regression, SVD and Elastic-Net not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as decision trees and matrix factorizations. We suggest an algorithm that gets a finite set of $n$ $d$-dimensional real vectors and returns a weighted subset of $d+1$ vectors whose sum is \emph{exactly} the same. The proof in Caratheodory's Theorem (1907) computes such a subset in $O(n^2d^2)$ time and thus not used in practice. Our algorithm computes this subset in $O(nd)$ time, using $O(\log n)$ calls to Caratheodory's construction on small but "smart" subsets. This is based on a novel paradigm of fusion between different data summarization techniques, known as sketches and coresets. As an example application, we show how it can be used to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed (big) data is trivial. Extensive experimental results and complete open source code are also provided.

NeurIPS Conference 2019 Conference Paper

k-Means Clustering of Lines for Big Data

• Yair Marom
• Dan Feldman

The input to the \emph{$k$-mean for lines} problem is a set $L$ of $n$ lines in $\mathbb{R}^d$, and the goal is to compute a set of $k$ centers (points) in $\mathbb{R}^d$ that minimizes the sum of squared distances over every line in $L$ and its nearest center. This is a straightforward generalization of the $k$-mean problem where the input is a set of $n$ points instead of lines. We suggest the first PTAS that computes a $(1+\epsilon)$-approximation to this problem in time $O(n \log n)$ for any constant approximation error $\epsilon \in (0, 1)$, and constant integers $k, d \geq 1$. This is by proving that there is always a weighted subset (called coreset) of $dk^{O(k)}\log (n)/\epsilon^2$ lines in $L$ that approximates the sum of squared distances from $L$ to \emph{any} given set of $k$ points. Using traditional merge-and-reduce technique, this coreset implies results for a streaming set (possibly infinite) of lines to $M$ machines in one pass (e. g. cloud) using memory, update time and communication that is near-logarithmic in $n$, as well as deletion of any line but using linear space. These results generalized for other distance functions such as $k$-median (sum of distances) or ignoring farthest $m$ lines from the given centers to handle outliers. Experimental results on 10 machines on Amazon EC2 cloud show that the algorithm performs well in practice. Open source code for all the algorithms and experiments is also provided.

JMLR Journal 2018 Journal Article

Training Gaussian Mixture Models at Scale via Coresets

• Mario Lucic
• Matthew Faulkner
• Andreas Krause
• Dan Feldman

How can we train a statistical mixture model on a massive data set? In this work we show how to construct \emph{coresets} for mixtures of Gaussians. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size polynomial in dimension and the number of mixture components, while being \emph{independent} of the data set size. Hence, one can harness computationally intensive algorithms to compute a good approximation on a significantly smaller data set. More importantly, such coresets can be efficiently constructed both in distributed and streaming settings and do not impose restrictions on the data generating process. Our results rely on a novel reduction of statistical estimation to problems in computational geometry and new combinatorial complexity results for mixtures of Gaussians. Empirical evaluation on several real- world data sets suggests that our coreset-based approach enables significant reduction in training-time with negligible approximation error. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

ICML Conference 2017 Conference Paper

Coresets for Vector Summarization with Applications to Network Graphs

• Dan Feldman
• Sedat Ozer
• Daniela Rus

We provide a deterministic data summarization algorithm that approximates the mean $\bar{p}=\frac{1}{n}\sum_{p\in P} p$ of a set $P$ of $n$ vectors in $\mathbb{R}^d$, by a weighted mean $\tilde{p}$ of a subset of $O(1/\epsilon)$ vectors, i. e. , independent of both $n$ and $d$. We prove that the squared Euclidean distance between $\bar{p}$ and $\tilde{p}$ is at most $\epsilon$ multiplied by the variance of $P$. We use this algorithm to maintain an approximated sum of vectors from an unbounded stream, using memory that is independent of $d$, and logarithmic in the $n$ vectors seen so far. Our main application is to extract and represent in a compact way friend groups and activity summaries of users from underlying data exchanges. For example, in the case of mobile networks, we can use GPS traces to identify meetings; in the case of social networks, we can use information exchange to identify friend groups. Our algorithm provably identifies the Heavy Hitter entries in a proximity (adjacency) matrix. The Heavy Hitters can be used to extract and represent in a compact way friend groups and activity summaries of users from underlying data exchanges. We evaluate the algorithm on several large data sets.

NeurIPS Conference 2016 Conference Paper

Dimensionality Reduction of Massive Sparse Datasets Using Coresets

• Dan Feldman
• Mikhail Volkov
• Daniela Rus

In this paper we present a practical solution with performance guarantees to the problem of dimensionality reduction for very large scale sparse matrices. We show applications of our approach to computing the Principle Component Analysis (PCA) of any $n\times d$ matrix, using one pass over the stream of its rows. Our solution uses coresets: a scaled subset of the $n$ rows that approximates their sum of squared distances to \emph{every} $k$-dimensional \emph{affine} subspace. An open theoretical problem has been to compute such a coreset that is independent of both $n$ and $d$. An open practical problem has been to compute a non-trivial approximation to the PCA of very large but sparse databases such as the Wikipedia document-term matrix in a reasonable time. We answer both of these questions affirmatively. Our main technical result is a new framework for deterministic coreset constructions based on a reduction to the problem of counting items in a stream.

ICRA Conference 2015 Conference Paper

Coresets for visual summarization with applications to loop closure

• Mikhail Volkov 0002
• Guy Rosman
• Dan Feldman
• John W. Fisher III
• Daniela Rus

In continuously operating robotic systems, efficient representation of the previously seen camera feed is crucial. Using a highly efficient compression coreset method, we formulate a new method for hierarchical retrieval of frames from large video streams collected online by a moving robot. We demonstrate how to utilize the resulting structure for efficient loop-closure by a novel sampling approach that is adaptive to the structure of the video. The same structure also allows us to create a highly-effective search tool for large-scale videos, which we demonstrate in this paper. We show the efficiency of proposed approaches for retrieval and loop closure on standard datasets, and on a large-scale video from a mobile camera.

NeurIPS Conference 2014 Conference Paper

Coresets for k-Segmentation of Streaming Data

• Guy Rosman
• Mikhail Volkov
• Dan Feldman
• John Fisher III
• Daniela Rus

Life-logging video streams, financial time series, and Twitter tweets are a few examples of high-dimensional signals over practically unbounded time. We consider the problem of computing optimal segmentation of such signals by k-piecewise linear function, using only one pass over the data by maintaining a coreset for the signal. The coreset enables fast further analysis such as automatic summarization and analysis of such signals. A coreset (core-set) is a compact representation of the data seen so far, which approximates the data well for a specific task -- in our case, segmentation of the stream. We show that, perhaps surprisingly, the segmentation problem admits coresets of cardinality only linear in the number of segments k, independently of both the dimension d of the signal, and its number n of points. More precisely, we construct a representation of size O(klog n /eps^2) that provides a (1+eps)-approximation for the sum of squared distances to any given k-piecewise linear function. Moreover, such coresets can be constructed in a parallel streaming approach. Our results rely on a novel eduction of statistical estimations to problems in computational geometry. We empirically evaluate our algorithms on very large synthetic and real data sets from GPS, video and financial domains, using 255 machines in Amazon cloud.

ICRA Conference 2014 Conference Paper

Visual precis generation using coresets

• Rohan Paul
• Dan Feldman
• Daniela Rus
• Paul Newman 0001

Given an image stream, our on-line algorithm will select the semantically-important images that summarize the visual experience of a mobile robot. Our approach consists of data pre-clustering using coresets followed by a graph based incremental clustering procedure using a topic based image representation. A coreset for an image stream is a set of representative images that semantically compresses the data corpus, in the sense that every frame has a similar representative image in the coreset. We prove that our algorithm efficiently computes the smallest possible coreset under natural well-defined similarity metric and up to provably small approximation factor. The output visual summary is computed via a hierarchical tree of coresets for different parts of the image stream. This allows multi-resolution summarization (or a video summary of specified duration) in the batch setting and a memory-efficient incremental summary for the streaming case.

ICRA Conference 2013 Conference Paper

K-robots clustering of moving sensors using coresets

• Dan Feldman
• Stephanie Gil
• Ross A. Knepper
• Brian J. Julian
• Daniela Rus

We present an approach to position k servers (e. g. mobile robots) to provide a service to n independently moving clients; for example, in mobile ad-hoc networking applications where inter-agent distances need to be minimized, connectivity constraints exist between servers, and no a priori knowledge of the clients' motion can be assumed. Our primary contribution is an algorithm to compute and maintain a small representative set, called a kinematic coreset, of the n moving clients. We prove that, in any given moment, the maximum distance between the clients and any set of k servers is approximated by the coreset up to a factor of (1 ± ε), where ε > 0 is an arbitrarily small constant. We prove that both the size of our coreset and its update time is polynomial in k log(n)/ε. Although our optimization problem is NP-hard (i. e. , takes time exponential in the number of servers to solve), solving it on the small coreset instead of the original clients results in a tractable controller. The approach is validated in a small scale hardware experiment using robot servers and human clients, and in a large scale numerical simulation using thousands of clients.

SODA Conference 2013 Conference Paper

Turning big data into tiny data: Constant-size coresets for k -means, PCA and projective clustering

• Dan Feldman
• Melanie Schmidt 0001
• Christian Sohler

IROS Conference 2012 Conference Paper

Communication coverage for independently moving robots

• Stephanie Gil
• Dan Feldman
• Daniela Rus

We consider the task of providing communication coverage to a group of sensing robots (sensors) moving independently to collect data. We provide communication via controlled placement of router vehicles that relay messages from any sensor to any other sensor in the system under the assumptions of 1) no cooperation from the sensors, and 2) only sensor-router or router-router communication over a maximum distance of R is reliable. We provide a formal framework and design provable exact and approximate (faster) algorithms for finding optimal router vehicle locations that are updated according to sensor movement. Using vehicle limitations, such as bounded control effort and maximum velocities of the sensors, our algorithm approximates areas that each router can reach while preserving connectivity and returns an expiration time window over which these positions are guaranteed to maintain communication of the entire system. The expiration time is compared against computation time required to update positions as a decision variable for choosing either the exact or approximate solution for maintaining connectivity with the sensors on-line.

SODA Conference 2012 Conference Paper

Data reduction for weighted and outlier-resistant clustering

• Dan Feldman
• Leonard J. Schulman

IROS Conference 2012 Conference Paper

Trajectory clustering for motion prediction

• Cynthia R. Sung
• Dan Feldman
• Daniela Rus

We investigate a data-driven approach to robotic path planning and analyze its performance in the context of interception tasks. Trajectories of moving objects often contain repeated patterns of motion, and learning those patterns can yield interception paths that succeed more often. We therefore propose an original trajectory clustering algorithm for extracting motion patterns from trajectory data and demonstrate its effectiveness over the more common clustering approach of using k-means. We use the results to build a Hidden Markov Model of a target's motion and predict movement. Our simulations show that these predictions lead to more effective interception. The results of this work have potential applications in coordination of multi-robot systems, tracking and surveillance tasks, and dynamic obstacle avoidance.

STOC Conference 2011 Conference Paper

A unified framework for approximating and clustering data

• Dan Feldman
• Michael Langberg

NeurIPS Conference 2011 Conference Paper

Scalable Training of Mixture Models via Coresets

• Dan Feldman
• Matthew Faulkner
• Andreas Krause

How can we train a statistical mixture model on a massive data set? In this paper, we show how to construct coresets for mixtures of Gaussians and natural generalizations. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset will also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size independent of the size of the data set. More precisely, we prove that a weighted set of $O(dk^3/\eps^2)$ data points suffices for computing a $(1+\eps)$-approximation for the optimal model on the original $n$ data points. Moreover, such coresets can be efficiently constructed in a map-reduce style computation, as well as in a streaming setting. Our results rely on a novel reduction of statistical estimation to problems in computational geometry, as well as new complexity results about mixtures of Gaussians. We empirically evaluate our algorithms on several real data sets, including a density estimation problem in the context of earthquake detection using accelerometers in mobile phones.

SODA Conference 2010 Conference Paper

Coresets and Sketches for High Dimensional Subspace Approximation Problems

• Dan Feldman
• Morteza Monemizadeh
• Christian Sohler
• David P. Woodruff

We consider the problem of approximating a set P of n points in ℝ d by a j-dimensional subspace under the ℓ p measure, in which we wish to minimize the sum of ℓ p distances from each point of P to this subspace. More generally, the F q (ℓ p )-subspace approximation problem asks for a j-subspace that minimizes the sum of qth powers of ℓ p -distances to this subspace, up to a multiplicative factor of (1 + ε). We develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i. e. small space representations that approximate the input point set P with respect to the subspace approximation problem. Our results are: A dimensionality reduction method that can be applied to F q (ℓ p )-clustering and shape fitting problems, such as those in [8, 15]. The first strong coreset for F 1 (ℓ 2 )-subspace approximation in high-dimensional spaces, i. e. of size polynomial in the dimension of the space. This coreset approximates the distances to any j-subspace (not just the optimal one). A (1 + ε)-approximation algorithm for the j-dimensional F 1 (ℓ 2 )-subspace approximation problem with running time nd(j/ε) O(1) + (n + d)2 poly(j/ε). A streaming algorithm that maintains a coreset for the F 1 (ℓ 2 )-subspace approximation problem and uses a space of (weighted) points. Streaming algorithms for the above problems with bounded precision in the turnstile model, i. e, when coordinates appear in an arbitrary order and undergo multiple updates. We show that bounded precision can lead to further improvements. We extend results of [7] for approximate linear regression, distances to subspace approximation, and optimal rank-j approximation, to error measures other than the Frobenius norm.

STOC Conference 2009 Conference Paper

Private coresets

• Dan Feldman
• Amos Fiat
• Haim Kaplan
• Kobbi Nissim

FOCS Conference 2006 Conference Paper

Coresets forWeighted Facilities and Their Applications

• Dan Feldman
• Amos Fiat
• Micha Sharir

We develop efficient (1 + epsiv)-approximation algorithms for generalized facility location problems. Such facilities are not restricted to being points in Ropf, and can represent more complex structures such as linear facilities (lines in Ropf d, j-dimensional flats), etc. We introduce coresets for weighted (point) facilities. These prove to be useful for such generalized facility location problems, and provide efficient algorithms for their construction. Applications include: k-mean and k-median generalizations, i. e. , find k lines that minimize the sum (or sum of squares) of the distances from each input point to its nearest line. Other applications are generalizations of linear regression problems to multiple regression lines, new SVD/PCA generalizations, and many more. The results significantly improve on previous work, which deals efficiently only with special cases. Open source code for the algorithms in this paper is also available