BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jinhui Xu

Jinhui Xu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Machine LearningCryptography and SecurityComputer VisionComputational GeometryData Structures and AlgorithmsArtificial IntelligenceComputational ComplexityNeural and Evolutionary Computing

Catalog footprint

What is connected

19works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2022arXiv

Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guarantees

(Gradient) Expectation Maximization (EM) is a widely used algorithm for estimating the maximum likelihood of mixture models or incomplete data problems. A major challenge facing this popular technique is how to effectively preserve the privacy of sensitive data. Previous research on this problem has already lead to the discovery of some Differentially Private (DP) algorithms for (Gradient) EM. However, unlike in the non-private case, existing techniques are not yet able to provide finite sample statistical guarantees. To address this issue, we propose in this paper the first DP version of (Gradient) EM algorithm with statistical guarantees. Moreover, we apply our general framework to three canonical models: Gaussian Mixture Model (GMM), Mixture of Regressions Model (MRM) and Linear Regression with Missing Covariates (RMC). Specifically, for GMM in the DP model, our estimation error is near optimal in some cases. For the other two models, we provide the first finite sample statistical guarantees. Our theory is supported by thorough numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed Data

We study the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) with heavy-tailed data. Specifically, we focus on the $\ell_1$-norm linear regression in the $ε$-DP model. While most of the previous work focuses on the case where the loss function is Lipschitz, here we only need to assume the variates has bounded moments. Firstly, we study the case where the $\ell_2$ norm of data has bounded second order moment. We propose an algorithm which is based on the exponential mechanism and show that it is possible to achieve an upper bound of $\tilde{O}(\sqrt{\frac{d}{nε}})$ (with high probability). Next, we relax the assumption to bounded $θ$-th order moment with some $θ\in (1, 2)$ and show that it is possible to achieve an upper bound of $\tilde{O}(({\frac{d}{nε}})^\frac{θ-1}θ)$. Our algorithms can also be extended to more relaxed cases where only each coordinate of the data has bounded moments, and we can get an upper bound of $\tilde{O}({\frac{d}{\sqrt{nε}}})$ and $\tilde{O}({\frac{d}{({nε})^\frac{θ-1}θ}})$ in the second and $θ$-th moment case respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data

In this paper, we study the problem of estimating smooth Generalized Linear Models (GLMs) in the Non-interactive Local Differential Privacy (NLDP) model. Different from its classical setting, our model allows the server to access some additional public but unlabeled data. In the first part of the paper we focus on GLMs. Specifically, we first consider the case where each data record is i.i.d. sampled from a zero-mean multivariate Gaussian distribution. Motivated by the Stein's lemma, we present an $(ε, δ)$-NLDP algorithm for GLMs. Moreover, the sample complexity of public and private data for the algorithm to achieve an $\ell_2$-norm estimation error of $α$ (with high probability) is ${O}(p α^{-2})$ and $\tilde{O}(p^3α^{-2}ε^{-2})$ respectively, where $p$ is the dimension of the feature vector. This is a significant improvement over the previously known exponential or quasi-polynomial in $α^{-1}$, or exponential in $p$ sample complexities of GLMs with no public data. Then we consider a more general setting where each data record is i.i.d. sampled from some sub-Gaussian distribution with bounded $\ell_1$-norm. Based on a variant of Stein's lemma, we propose an $(ε, δ)$-NLDP algorithm for GLMs whose sample complexity of public and private data to achieve an $\ell_\infty$-norm estimation error of $α$ is ${O}(p^2α^{-2})$ and $\tilde{O}(p^2α^{-2}ε^{-2})$ respectively, under some mild assumptions and if $α$ is not too small ({\em i.e.,} $α\geq Ω(\frac{1}{\sqrt{p}})$). In the second part of the paper, we extend our idea to the problem of estimating non-linear regressions and show similar results as in GLMs for both multivariate Gaussian and sub-Gaussian cases. Finally, we demonstrate the effectiveness of our algorithms through experiments on both synthetic and real-world datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Few-shot Learning as Cluster-induced Voronoi Diagrams: A Geometric Approach

Few-shot learning (FSL) is the process of rapid generalization from abundant base samples to inadequate novel samples. Despite extensive research in recent years, FSL is still not yet able to generate satisfactory solutions for a wide range of real-world applications. To confront this challenge, we study the FSL problem from a geometric point of view in this paper. One observation is that the widely embraced ProtoNet model is essentially a Voronoi Diagram (VD) in the feature space. We retrofit it by making use of a recent advance in computational geometry called Cluster-induced Voronoi Diagram (CIVD). Starting from the simplest nearest neighbor model, CIVD gradually incorporates cluster-to-point and then cluster-to-cluster relationships for space subdivision, which is used to improve the accuracy and robustness at multiple stages of FSL. Specifically, we use CIVD (1) to integrate parametric and nonparametric few-shot classifiers; (2) to combine feature representation and surrogate representation; (3) and to leverage feature-level, transformation-level, and geometry-level heterogeneities for a better ensemble. Our CIVD-based workflow enables us to achieve new state-of-the-art results on mini-ImageNet, CUB, and tiered-ImagenNet datasets, with ${\sim}2\%{-}5\%$ improvements upon the next best. To summarize, CIVD provides a mathematically elegant and geometrically interpretable framework that compensates for extreme data insufficiency, prevents overfitting, and allows for fast geometric ensemble for thousands of individual VD. These together make FSL stronger.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improving Uncertainty Calibration of Deep Neural Networks via Truth Discovery and Geometric Optimization

Deep Neural Networks (DNNs), despite their tremendous success in recent years, could still cast doubts on their predictions due to the intrinsic uncertainty associated with their learning process. Ensemble techniques and post-hoc calibrations are two types of approaches that have individually shown promise in improving the uncertainty calibration of DNNs. However, the synergistic effect of the two types of methods has not been well explored. In this paper, we propose a truth discovery framework to integrate ensemble-based and post-hoc calibration methods. Using the geometric variance of the ensemble candidates as a good indicator for sample uncertainty, we design an accuracy-preserving truth estimator with provably no accuracy drop. Furthermore, we show that post-hoc calibration can also be enhanced by truth discovery-regularized optimization. On large-scale datasets including CIFAR and ImageNet, our method shows consistent improvement against state-of-the-art calibration approaches on both histogram-based and kernel density-based evaluation metrics. Our codes are available at https://github.com/horsepurve/truly-uncertain.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

In-Range Farthest Point Queries and Related Problem in High Dimensions

Range-aggregate query is an important type of queries with numerous applications. It aims to obtain some structural information (defined by an aggregate function $F(\cdot)$) of the points (from a point set $P$) inside a given query range $B$. In this paper, we study the range-aggregate query problem in high dimensional space for two aggregate functions: (1) $F(P \cap B)$ is the farthest point in $P \cap B$ to a query point $q$ in $\mathbb{R}^d$ and (2) $F(P \cap B)$ is the minimum enclosing ball (MEB) of $P \cap B$. For problem (1), called In-Range Farthest Point (IFP) Query, we develop a bi-criteria approximation scheme: For any $ε>0$ that specifies the approximation ratio of the farthest distance and any $γ>0$ that measures the "fuzziness" of the query range, we show that it is possible to pre-process $P$ into a data structure of size $\tilde{O}_{ε,γ}(dn^{1+ρ})$ in $\tilde{O}_{ε,γ}(dn^{1+ρ})$ time such that given any $\mathbb{R}^d$ query ball $B$ and query point $q$, it outputs in $\tilde{O}_{ε,γ}(dn^ρ)$ time a point $p$ that is a $(1-ε)$-approximation of the farthest point to $q$ among all points lying in a $(1+γ)$-expansion $B(1+γ)$ of $B$, where $0<ρ<1$ is a constant depending on $ε$ and $γ$ and the hidden constants in big-O notations depend only on $ε$, $γ$ and $\text{Polylog}(nd)$. For problem (2), we show that the IFP result can be applied to develop query scheme with similar time and space complexities to achieve a $(1+ε)$-approximation for MEB.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

LAFITE: Towards Language-Free Training for Text-to-Image Generation

One of the major challenges in training text-to-image generation models is the need of a large number of high-quality image-text pairs. While image samples are often easily accessible, the associated text descriptions typically require careful human captioning, which is particularly time- and cost-consuming. In this paper, we propose the first work to train text-to-image generation models without any text data. Our method leverages the well-aligned multi-modal semantic space of the powerful pre-trained CLIP model: the requirement of text-conditioning is seamlessly alleviated via generating text features from image features. Extensive experiments are conducted to illustrate the effectiveness of the proposed method. We obtain state-of-the-art results in the standard text-to-image generation tasks. Importantly, the proposed language-free model outperforms most existing models trained with full image-text pairs. Furthermore, our method can be applied in fine-tuning pre-trained models, which saves both training time and cost in training text-to-image generation models. Our pre-trained model obtains competitive results in zero-shot text-to-image generation on the MS-COCO dataset, yet with around only 1% of the model size and training data size relative to the recently proposed large DALL-E model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Progressive Voronoi Diagram Subdivision: Towards A Holistic Geometric Framework for Exemplar-free Class-Incremental Learning

Exemplar-free Class-incremental Learning (CIL) is a challenging problem because rehearsing data from previous phases is strictly prohibited, causing catastrophic forgetting of Deep Neural Networks (DNNs). In this paper, we present iVoro, a holistic framework for CIL, derived from computational geometry. We found Voronoi Diagram (VD), a classical model for space subdivision, is especially powerful for solving the CIL problem, because VD itself can be constructed favorably in an incremental manner -- the newly added sites (classes) will only affect the proximate classes, making the non-contiguous classes hardly forgettable. Further, in order to find a better set of centers for VD construction, we colligate DNN with VD using Power Diagram and show that the VD structure can be optimized by integrating local DNN models using a divide-and-conquer algorithm. Moreover, our VD construction is not restricted to the deep feature space, but is also applicable to multiple intermediate feature spaces, promoting VD to be multi-centered VD (CIVD) that efficiently captures multi-grained features from DNN. Importantly, iVoro is also capable of handling uncertainty-aware test-time Voronoi cell assignment and has exhibited high correlations between geometric uncertainty and predictive accuracy (up to ~0.9). Putting everything together, iVoro achieves up to 25.26%, 37.09%, and 33.21% improvements on CIFAR-100, TinyImageNet, and ImageNet-Subset, respectively, compared to the state-of-the-art non-exemplar CIL approaches. In conclusion, iVoro enables highly accurate, privacy-preserving, and geometrically interpretable CIL that is particularly useful when cross-phase data sharing is forbidden, e.g. in medical applications. Our code is available at https://machunwei.github.io/ivoro.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Meta-Learning with Neural Tangent Kernels

Model Agnostic Meta-Learning (MAML) has emerged as a standard framework for meta-learning, where a meta-model is learned with the ability of fast adapting to new tasks. However, as a double-looped optimization problem, MAML needs to differentiate through the whole inner-loop optimization path for every outer-loop training step, which may lead to both computational inefficiency and sub-optimal solutions. In this paper, we generalize MAML to allow meta-learning to be defined in function spaces, and propose the first meta-learning paradigm in the Reproducing Kernel Hilbert Space (RKHS) induced by the meta-model's Neural Tangent Kernel (NTK). Within this paradigm, we introduce two meta-learning algorithms in the RKHS, which no longer need a sub-optimal iterative inner-loop adaptation as in the MAML framework. We achieve this goal by 1) replacing the adaptation with a fast-adaptive regularizer in the RKHS; and 2) solving the adaptation analytically based on the NTK theory. Extensive experimental studies demonstrate advantages of our paradigm in both efficiency and quality of solutions compared to related meta-learning algorithms. Another interesting feature of our proposed methods is that they are demonstrated to be more robust to adversarial attacks and out-of-distribution adaptation than popular baselines, as demonstrated in our experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph Neural Networks with Composite Kernels

Learning on graph structured data has drawn increasing interest in recent years. Frameworks like Graph Convolutional Networks (GCNs) have demonstrated their ability to capture structural information and obtain good performance in various tasks. In these frameworks, node aggregation schemes are typically used to capture structural information: a node's feature vector is recursively computed by aggregating features of its neighboring nodes. However, most of aggregation schemes treat all connections in a graph equally, ignoring node feature similarities. In this paper, we re-interpret node aggregation from the perspective of kernel weighting, and present a framework to consider feature similarity in an aggregation scheme. Specifically, we show that normalized adjacency matrix is equivalent to a neighbor-based kernel matrix in a Krein Space. We then propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space. We further show how the proposed method can be extended to Graph Attention Network (GAT). Experimental results demonstrate better performance of our proposed framework in several real-world applications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

KernelNet: A Data-Dependent Kernel Parameterization for Deep Generative Modeling

Learning with kernels is an important concept in machine learning. Standard approaches for kernel methods often use predefined kernels that require careful selection of hyperparameters. To mitigate this burden, we propose in this paper a framework to construct and learn a data-dependent kernel based on random features and implicit spectral distributions that are parameterized by deep neural networks. The constructed network (called KernelNet) can be applied to deep generative modeling in various scenarios, including two popular learning paradigms in deep generative models, MMD-GAN and implicit Variational Autoencoder (VAE). We show that our proposed kernel indeed exists in applications and is guaranteed to be positive definite. Furthermore, the induced Maximum Mean Discrepancy (MMD) can endow the continuity property in weak topology by simple regularization. Extensive experiments indicate that our proposed KernelNet consistently achieves better performance compared to related methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations

Minimizing a convex risk function is the main step in many basic learning algorithms. We study protocols for convex optimization which provably leak very little about the individual data points that constitute the loss function. Specifically, we consider differentially private algorithms that operate in the local model, where each data record is stored on a separate user device and randomization is performed locally by those devices. We give new protocols for \emph{noninteractive} LDP convex optimization---i.e., protocols that require only a single randomized report from each user to an untrusted aggregator. We study our algorithms' performance with respect to expected loss---either over the data set at hand (empirical risk) or a larger population from which our data set is assumed to be drawn. Our error bounds depend on the form of individuals' contribution to the expected loss. For the case of \emph{generalized linear losses} (such as hinge and logistic losses), we give an LDP algorithm whose sample complexity is only linear in the dimensionality $p$ and quasipolynomial in other terms (the privacy parameters $ε$ and $δ$, and the desired excess risk $α$). This is the first algorithm for nonsmooth losses with sub-exponential dependence on $p$. For the Euclidean median problem, where the loss is given by the Euclidean distance to a given data point, we give a protocol whose sample complexity grows quasipolynomially in $p$. This is the first protocol with sub-exponential dependence on $p$ for a loss that is not a generalized linear loss . Our result for the hinge loss is based on a technique, dubbed polynomial of inner product approximation, which may be applicable to other problems. Our results for generalized linear losses and the Euclidean median are based on new reductions to the case of hinge loss.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness

As a certified defensive technique, randomized smoothing has received considerable attention due to its scalability to large datasets and neural networks. However, several important questions remain unanswered, such as (i) whether the Gaussian mechanism is an appropriate option for certifying $\ell_2$-norm robustness, and (ii) whether there is an appropriate randomized (smoothing) mechanism to certify $\ell_\infty$-norm robustness. To shed light on these questions, we argue that the main difficulty is how to assess the appropriateness of each randomized mechanism. In this paper, we propose a generic framework that connects the existing frameworks in \cite{lecuyer2018certified, li2019certified}, to assess randomized mechanisms. Under our framework, for a randomized mechanism that can certify a certain extent of robustness, we define the magnitude of its required additive noise as the metric for assessing its appropriateness. We also prove lower bounds on this metric for the $\ell_2$-norm and $\ell_\infty$-norm cases as the criteria for assessment. Based on our framework, we assess the Gaussian and Exponential mechanisms by comparing the magnitude of additive noise required by these mechanisms and the lower bounds (criteria). We first conclude that the Gaussian mechanism is indeed an appropriate option to certify $\ell_2$-norm robustness. Surprisingly, we show that the Gaussian mechanism is also an appropriate option for certifying $\ell_\infty$-norm robustness, instead of the Exponential mechanism. Finally, we generalize our framework to $\ell_p$-norm for any $p\geq2$. Our theoretical findings are verified by evaluations on CIFAR10 and ImageNet.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Deep Extreme Feature Extraction: New MVA Method for Searching Particles in High Energy Physics

In this paper, we present Deep Extreme Feature Extraction (DEFE), a new ensemble MVA method for searching $τ^{+}τ^{-}$ channel of Higgs bosons in high energy physics. DEFE can be viewed as a deep ensemble learning scheme that trains a strongly diverse set of neural feature learners without explicitly encouraging diversity and penalizing correlations. This is achieved by adopting an implicit neural controller (not involved in feedforward compuation) that directly controls and distributes gradient flows from higher level deep prediction network. Such model-independent controller results in that every single local feature learned are used in the feature-to-output mapping stage, avoiding the blind averaging of features. DEFE makes the ensembles 'deep' in the sense that it allows deep post-process of these features that tries to learn to select and abstract the ensemble of neural feature learners. With the application of this model, a selection regions full of signal process can be obtained through the training of a miniature collision events set. In comparison of the Classic Deep Neural Network, DEFE shows a state-of-the-art performance: the error rate has decreased by about 37\%, the accuracy has broken through 90\% for the first time, along with the discovery significance has reached a standard deviation of 6.0 $σ$. Experimental data shows that, DEFE is able to train an ensemble of discriminative feature learners that boosts the overperformance of final prediction.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On DDoS Attack Related Minimum Cut Problems

In this paper, we study two important extensions of the classical minimum cut problem, called {\em Connectivity Preserving Minimum Cut (CPMC)} problem and {\em Threshold Minimum Cut (TMC)} problem, which have important applications in large-scale DDoS attacks. In CPMC problem, a minimum cut is sought to separate a of source from a destination node and meanwhile preserve the connectivity between the source and its partner node(s). The CPMC problem also has important applications in many other areas such as emergency responding, image processing, pattern recognition, and medical sciences. In TMC problem, a minimum cut is sought to isolate a target node from a threshold number of partner nodes. TMC problem is an important special case of network inhibition problem and has important applications in network security. We show that the general CPMC problem cannot be approximated within $logn$ unless $NP=P$ has quasi-polynomial algorithms. We also show that a special case of two group CPMC problem in planar graphs can be solved in polynomial time. The corollary of this result is that the network diversion problem in planar graphs is in $P$, a previously open problem. We show that the threshold minimum node cut (TMNC) problem can be approximated within ratio $O(\sqrt{n})$ and the threshold minimum edge cut problem (TMEC) can be approximated within ratio $O(\log^2{n})$. \emph{We also answer another long standing open problem: the hardness of the network inhibition problem and network interdiction problem. We show that both of them cannot be approximated within any constant ratio. unless $NP \nsubseteq \cap_{δ>0} BPTIME(2^{n^δ})$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Algorithms for Cut Problems on Trees

We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that runs in time $O^{*}(ρ^k)$, where $ρ= \sqrt{\sqrt{2} + 1} \approx 1.555$ is the positive root of the polynomial $x^4-2x^2-1$. This improves the current-best algorithm of Chen et al. that runs in time $O^{*}(1.619^k)$. For the {\sc generalized multiway cut on trees} problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the {\sc generalized multiway cut on trees} problem to the {\sc multicut on trees} problem, our results give a parameterized algorithm that solves the {\sc generalized multiway cut on trees} problem in time $O^{*}(ρ^k)$, where $ρ= \sqrt{\sqrt{2} + 1} \approx 1.555$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Connectivity Preserving Minimum Cut Problem

In this paper, we study a generalization of the classical minimum cut prob- lem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). The CPMC problem is a rather powerful formulation for a set of problems and finds applications in many other areas, such as network security, image processing, data mining, pattern recognition, and machine learning. For this important problem, we consider two variants, connectiv- ity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be ap- proximated within αlogn for some constant α unless P=NP, and cannot be approximated within any poly(logn) unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. Particularly, we show that polynomial time solutions exist for CPMEC in planar graphs and for CPMNC in some special planar graphs. The hardness of CPMEC in general graphs remains open, but the polynomial time algorithm in planar graphs still has important practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Chromatic Clustering in High Dimensional Space

In this paper, we study a new type of clustering problem, called {\em Chromatic Clustering}, in high dimensional space. Chromatic clustering seeks to partition a set of colored points into groups (or clusters) so that no group contains points with the same color and a certain objective function is optimized. In this paper, we consider two variants of the problem, chromatic $k$-means clustering (denoted as $k$-CMeans) and chromatic $k$-medians clustering (denoted as $k$-CMedians), and investigate their hardness and approximation solutions. For $k$-CMeans, we show that the additional coloring constraint destroys several key properties (such as the locality property) used in existing $k$-means techniques (for ordinary points), and significantly complicates the problem. There is no FPTAS for the chromatic clustering problem, even if $k=2$. To overcome the additional difficulty, we develop a standalone result, called {\em Simplex Lemma}, which enables us to efficiently approximate the mean point of an unknown point set through a fixed dimensional simplex. A nice feature of the simplex is its independence with the dimensionality of the original space, and thus can be used for problems in very high dimensional space. With the simplex lemma, together with several random sampling techniques, we show that a $(1+ε)$-approximation of $k$-CMeans can be achieved in near linear time through a sphere peeling algorithm. For $k$-CMedians, we show that a similar sphere peeling algorithm exists for achieving constant approximation solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Linear Time Algorithm for Projective Clustering

Projective clustering is a problem with both theoretical and practical importance and has received a great deal of attentions in recent years. Given a set of points $P$ in $\mathbb{R}^{d}$ space, projective clustering is to find a set $\mathbb{F}$ of $k$ lower dimensional $j$-flats so that the average distance (or squared distance) from points in $P$ to their closest flats is minimized. Existing approaches for this problem are mainly based on adaptive/volume sampling or core-sets techniques which suffer from several limitations. In this paper, we present the first uniform random sampling based approach for this challenging problem and achieve linear time solutions for three cases, general projective clustering, regular projective clustering, and $L_τ$ sense projective clustering. For the general projective clustering problem, we show that for any given small numbers $0<γ, ε<1$, our approach first removes $γ|P|$ points as outliers and then determines $k$ $j$-flats to cluster the remaining points into $k$ clusters with an objective value no more than $(1+ε)$ times of the optimal for all points. For regular projective clustering, we demonstrate that when the input points satisfy some reasonable assumption on its input, our approach for the general case can be extended to yield a PTAS for all points. For $L_τ$ sense projective clustering, we show that our techniques for both the general and regular cases can be naturally extended to the $L_τ$ sense projective clustering problem for any $1 \le τ< \infty$. Our results are based on several novel techniques, such as slab partition, $Δ$-rotation, symmetric sampling, and recursive projection, and can be easily implemented for applications.

0 citations0 reviewsNo code linkedOpen access