We consider the problem of embedding a finite set of points @math that satisfy @math triangle inequalities into @math , when the points are approximately low-dimensional. Goemans (unpublished, appears in a work of [Magen and Moharammi, 2008]) showed that such points residing in @math dimensions can be embedded into @math with distortion at most @math . We prove the following robust analogue of this statement: if there exists a @math -dimensional subspace @math such that the projections onto this subspace satisfy @math , then there is an embedding of the points into @math with @math average distortion. A consequence of this result is that the integrality gap of the well-known Goemans-Linial SDP relaxation for the Uniform Sparsest Cut problem is @math on graphs @math whose @math -th smallest normalized eigenvalue of the Laplacian satisfies @math . Our result improves upon the previously known bound of @math on the average distortion, and the integrality gap of the Goemans-Linial SDP under the same preconditions, proven in the previous works of [Deshpande and Venkat, 2014] and [Deshpande, Harsha and Venkat, 2016].
Let (G) be the minimum conductance of an undirected graph G, and let 0= = 2, (G) = O(k) , and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if $ is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.