Convexity-Driven Projection for Point Cloud Dimensionality Reduction
This work addresses dimensionality reduction for point cloud data, offering verifiable guarantees for practitioners, but it appears incremental as it builds on existing graph-based methods.
The authors tackled the problem of dimensionality reduction for point clouds by proposing Convexity-Driven Projection (CDP), a boundary-free linear method that preserves detour-induced local non-convexity, with results including pairwise a-posteriori certificates and average-case spectral bounds for distortion.
We propose Convexity-Driven Projection (CDP), a boundary-free linear method for dimensionality reduction of point clouds that targets preserving detour-induced local non-convexity. CDP builds a $k$-NN graph, identifies admissible pairs whose Euclidean-to-shortest-path ratios are below a threshold, and aggregates their normalized directions to form a positive semidefinite non-convexity structure matrix. The projection uses the top-$k$ eigenvectors of the structure matrix. We give two verifiable guarantees. A pairwise a-posteriori certificate that bounds the post-projection distortion for each admissible pair, and an average-case spectral bound that links expected captured direction energy to the spectrum of the structure matrix, yielding quantile statements for typical distortion. Our evaluation protocol reports fixed- and reselected-pairs detour errors and certificate quantiles, enabling practitioners to check guarantees on their data.