Ibrahim Jubran

Mr. Ibrahim Jubran


Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
11 January 2022 in IEEE Transactions on Pattern Analysis and Machine Intelligence
Verified
Journal Article
Closed access
AMAlaa Maalouf
Alaa Maalouf
Ibrahim JubranIbrahim Jubran
Ibrahim Jubran
DFDan Feldman
Dan Feldman
Least-mean-squares (LMS) solvers such as Linear / Ridge-Regression and SVD not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as matrix factorizations. We suggest an algorithm that gets a finite set of n $d$ -dimensional real vectors and returns a subset of $d+1$ vectors with positive weights whose weighted sum is \emph{exactly} the same. The constructive proof in Caratheodory's Theorem computes such a subset in $O(n^2d^2)$ time and thus not used in practice. Our algorithm computes this subset in $O(nd+d^4\log{n})$ 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. For large values of d, we suggest a faster construction that takes $O(nd)$ time and returns a weighted subset of $O(d)$ sparsified input points. Here, a sparsified point means that some of its entries were set to zero. As an application, we show how to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed data is trivial. Extensive experimental results and open source code are provided.

16 September 2021 in WIREs Data Mining and Knowledge Discovery
Verified
Journal Article
Closed access
PDF file
Ibrahim JubranIbrahim Jubran
Ibrahim Jubran
AMAlaa Maalouf
Alaa Maalouf
DFDan Feldman
Dan Feldman

16 March 2020 in IEEE Transactions on Knowledge and Data Engineering
Verified
Journal Article
Closed access
Ibrahim JubranIbrahim Jubran
Ibrahim Jubran
DFDan Feldman
Dan Feldman
We suggest a new optimization technique for minimizing the sum $\sum_{i=1}^n g_i(x)$ of $n$ non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-times are polynomial in $n$ for the fundamental problem of Points-to-Lines alignment: Given $n$ points $p_1,\cdots,\;p_n$ and $n$ lines $\ell_1,\;\cdots,\;\ell_n$ on the plane and $z>0$ , compute the matching $\pi:[n]\to[n]$ and alignment (rotation matrix $R$ and translation vector $t$ ) that minimize the sum of Euclidean distances $\sum_{i=1}^n \mathrm{dist}(Rp_i-t,\ell_{\pi(i)})^z$ between each point to its corresponding line. This problem is non-trivial even if $z=1$ and the matching $\pi$ is given. If $\pi$ is given, our algorithms run in $O(n^3)$ time, and even near-linear in $n$ using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g. outliers or pseudo-distances such as $M$ -estimators for the problem are also provided. Experimental results and open source code show that our algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems.

19 October 2019 in arXiv
Verified
Preprint
Open access
PDF file
Ibrahim JubranIbrahim Jubran
Ibrahim Jubran
AMAlaa Maalouf
Alaa Maalouf
DFDan Feldman
Dan Feldman
A coreset (or core-set) of an input set is its small summation, such that solving a problem on the coreset as its input, provably yields the same result as solving the same problem on the original (full) set, for a given family of problems (models, classifiers, loss functions). Over the past decade, coreset construction algorithms have been suggested for many fundamental problems in e.g. machine/deep learning, computer vision, graphics, databases, and theoretical computer science. This introductory paper was written following requests from (usually non-expert, but also colleagues) regarding the many inconsistent coreset definitions, lack of available source code, the required deep theoretical background from different fields, and the dense papers that make it hard for beginners to apply coresets and develop new ones. The paper provides folklore, classic and simple results including step-by-step proofs and figures, for the simplest (accurate) coresets of very basic problems, such as: sum of vectors, minimum enclosing ball, SVD/ PCA and linear regression. Nevertheless, we did not find most of their constructions in the literature. Moreover, we expect that putting them together in a retrospective context would help the reader to grasp modern results that usually extend and generalize these fundamental observations. Experts might appreciate the unified notation and comparison table that links between existing results. Open source code with example scripts are provided for all the presented algorithms, to demonstrate their practical usage, and to support the readers who are more familiar with programming than math.

9 March 2020 in arXiv
Verified
Preprint
Open access
PDF file
Ibrahim JubranIbrahim Jubran
Ibrahim Jubran
MTMurad Tukan
Murad Tukan
AMAlaa Maalouf
Alaa Maalouf
DFDan Feldman
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 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.

6 September 2020 in arXiv
Verified
Preprint
Open access
PDF file
AMAlaa Maalouf
Alaa Maalouf
Ibrahim JubranIbrahim Jubran
Ibrahim Jubran
DFDan Feldman
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+d^4\log{n})$ 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. For large values of $d$, we suggest a faster construction that takes $O(nd)$ time (linear in the input's size) and returns a weighted subset of $O(d)$ sparsified input points. Here, sparsified point means that some of its entries were replaced by zeroes. 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.