Sparse One-Grab Sampling with Probabilistic Guarantees.

Area of Science:

• Data Science
• Computer Vision
• Statistical Analysis

Background:

• Big data analysis relies on sampling for computational efficiency.
• Determining the minimum sample size for accurate representation of diverse data structures (e.g., clusters) is a significant challenge.
• Existing methods often require prior knowledge of data distribution or structure count.

Purpose of the Study:

• To propose a novel sampling method, Sparse Withdrawal of Inliers in a First Trial (SWIFT), for big data analysis.
• To guarantee a sufficient number of samples from each underlying data structure with high probability.
• To establish accurate lower and upper bounds for the minimal sample size, enabling sparse sampling strategies.

Main Methods:

• Developed the SWIFT method to determine the smallest sample size for a single-grab subset.
• Modeled the sampling problem using hypergeometric or multinomial probability mass functions (pmf).
• Derived mathematical bounds for sample size approximation, ensuring representation of underlying structures.

Main Results:

• SWIFT provides a sparse sampling strategy with a level of sparseness independent of population size.
• The method demonstrates robustness against a high number of outliers.
• Accurate mathematical bounds were derived, showing close proximity between lower and upper bounds in various scenarios.

Conclusions:

• SWIFT offers an effective solution for big data sampling, ensuring faithful representation of diverse structures with minimal samples.
• The method's independence from prior data distribution knowledge and its robustness to outliers make it broadly applicable.
• Evaluations in computer vision tasks like subspace clustering and structure from motion confirm SWIFT's accuracy and computational efficiency.