NDLI: Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Please wait, while we are loading the content...

Counting and Enumerating Crossing-free Geometric Graphs

A Framework for Computing the Greedy Spanner

There are Plane Spanners of Maximum Degree 4

New and Improved Spanning Ratios for Yao Graphs

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Progressive Geometric Algorithms

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp

The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems

Design of 3D printed mathematical art

Embeddability in the 3-sphere is decidable

The Connect-The-Dots Family of Puzzles: The Video

LiveCG: an Interactive Visualization Environment for Computational Geometry

Trajectory Grouping Structure: the Video

Visualizing hyperbolic Voronoi diagrams

Animation of an Algorithm for Drawing Graphs in 3D

Visualization of Floater and Gotsman's Morphing Algorithm

Geometric kth Shortest Paths: the Applet

Polytope Offsets and Straight Skeletons in 3D

Optimal Geometric Flows via Dual Programs

Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

Outerstring graphs are χ-bounded

Improved bounds for the conflict-free chromatic art gallery problem

Linear transformation distance for bichromatic matchings

Delaunay triangulations with disconnected realization spaces

Eliminating Tverberg Points, I. An Analogue of the Whitney Trick

Higher Dimensional Cheeger Inequalities

Incidences between points and lines in R4: Extended Abstract

On triple intersections of three families of unit circles

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage

Smallest enclosing ball for probabilistic data

Peeling Potatoes Near-Optimally in Near-Linear Time

On the Complexity of Randomly Weighted Voronoi Diagrams

A Census of Plane Graphs with Polyline Edges

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited

Using Convex Relaxations for Efficiently and Privately Releasing Marginals

Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Better embeddings for planar Earth-Mover Distance over sparse sets

Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained Delaunay Refinement

On the reconstruction of convex sets from random normal measurements

Intersection of paraboloids and application to Minkowski-type problems

Efficient Random-Walk Methods for Approximating Polytope Volume

The Persistent Homology of Distance Functions under Random Projection

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Computing Topological Persistence for Simplicial Maps

Induced Matchings of Barcodes and the Algebraic Stability of Persistence

Towards Expressive 3D Modeling: new challenges for geometric computing

Computing the Fréchet distance with shortcuts is NP-hard

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Light spanners for Snowflake Metrics

Continuously Flattening Polyhedra Using Straight Skeletons

Two-Point L1 Shortest Path Queries in the Plane

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Free Edge Lengths in Plane Graphs

Weight Balancing on Boundaries and Skeletons

Separation by Convex Pseudo-Circles

Euclidean Steiner Shallow-Light Trees

Measuring Distance between Reeb Graphs

Stochastic Convergence of Persistence Landscapes and Silhouettes

The Morse Theory of Čech and Delaunay Filtrations

Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph

Metric Embedding, Hyperbolic Space, and Social Networks

Sampling with Removal in LP-type Problems

Liftings and stresses for planar periodic frameworks

The Opaque Square

The JS-graphs of Join and Split Trees

Distinct distances on algebraic curves in the plane

Lower bounds on geometric Ramsey functions

Curves in Rd intersecting every hyperplane at most d + 1 times

Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Content Provider	ACM Digital Library
Author	Xu, Jinhui Ding, Hu
Abstract	Least Trimmed Squares (LTS) estimator is a statistical tool for estimating how well a set of points fits a hyperplane. As a robust alternative to the classical least squares estimator, LTS takes as input a set P of n points in Rd and a fitting parameter m ≤ n, and computes a non-vertical hyperplane H so that the sum of the m smallest squared vertical distances from P to H is minimized. Previous research has indicated that although solving LTS (exactly or approximately) could be quite costly (i.e., it may take Ω(nd™1) time to even approximate it when m/n is a positive constant c < 1), a hybrid version of approximation, which is a bi-criteria on residual approximation and quantile approximation, can be obtained in linear time in any fixed dimensional space. In this paper, we further show that an (&epsis;r, &epsis;q)-hybrid approximation of LTS can be computed in sub-linear time, where &epsis;r > 0 is the residual approximation ratio and 0 < &epsis;q < 1 is the quantile approximation ratio. The running time is independent of the input size n, when m = ⊝(n). Comparing to existing result, our approach has quite a few advantages, e.g., is much simpler, has better robustness, takes only constant additional space, and can deal with big data (e.g., streaming data). Our result is based on new insights to the problem and several novel techniques, such as recursive slab partition, sequential orthogonal rotation, and symmetric sampling. Our technique can also be extended to achieve sub-linear time hybrid approximations for several related problems, such as data-oblivious computation for LTS in Secure Multi-party Computation (SMC) protocol, LTS on uncertain and range data, and the Orthogonal Least Trimmed Squares (OLTS) problem. It is likely that our technique will be applicable to other shape fitting problems.
Starting Page	110
Ending Page	119
Page Count	10
File Format	PDF
ISBN	9781450325943
DOI	10.1145/2582112.2582131
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Secure multi-party computation Sub-linear time Least trimmed squares estimator Large scale data Uncertain data Robust linear regression
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in