Linear representation learning is widely studied due to its conceptual simplicity and empirical utility in tasks such as compression, classification, and feature extraction. Given a set of points \([\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n] = \mathbf{X} \in \mathbb{R}^{d \times n}\) and a vector \(\mathbf{y} \in \mathbb{R}^d\) , the goal is to find coefficients \(\mathbf{w} \in \mathbb{R}^n\) so that \(\mathbf{X} \mathbf{w} \approx \mathbf{y}\) , subject to some desired structure on \(\mathbf{w}\) . In this work we seek \(\mathbf{w}\) that forms a local reconstruction of \(\mathbf{y}\) by solving a regularized least squares regression problem. We obtain local solutions through a locality function that promotes the use of columns of \(\mathbf{X}\) that are close to \(\mathbf{y}\) when used as a regularization term. We prove that, for all levels of regularization and under a mild condition that the columns of \(\mathbf{X}\) have a unique Delaunay triangulation, the optimal coefficients’ number of non-zero entries is upper bounded by \(d+1\) , thereby providing local sparse solutions when \(d \ll n\) . Under the same condition we also show that for any \(\mathbf{y}\) contained in the convex hull of \(\mathbf{X}\) there exists a regime of regularization parameter such that the optimal coefficients are supported on the vertices of the Delaunay simplex containing \(\mathbf{y}\) . This provides an interpretation of the sparsity as having structure obtained implicitly from the Delaunay triangulation of \(\mathbf{X}\) . We demonstrate that our locality regularized problem can be solved in comparable time to other methods that identify the containing Delaunay simplex.
