This content will become publicly available on February 22, 2023

Sublinear Time Approximation of Text Similarity Matrices
We study algorithms for approximating pairwise similarity matrices that arise in natural language processing. Generally, computing a similarity matrix for $n$ data points requires $\Omega(n^2)$ similarity computations. This quadratic scaling is a significant bottleneck, especially when similarities are computed via expensive functions, e.g., via transformer models. Approximation methods reduce this quadratic complexity, often by using a small subset of exactly computed similarities to approximate the remainder of the complete pairwise similarity matrix. Significant work focuses on the efficient approximation of positive semidefinite (PSD) similarity matrices, which arise e.g., in kernel methods. However, much less is understood about indefinite (non-PSD) similarity matrices, which often arise in NLP. Motivated by the observation that many of these matrices are still somewhat close to PSD, we introduce a generalization of the popular \emph{Nystrom method} to the indefinite setting. Our algorithm can be applied to any similarity matrix and runs in sublinear time in the size of the matrix, producing a rank-$s$ approximation with just $O(ns)$ similarity computations. We show that our method, along with a simple variant of CUR decomposition, performs very well in approximating a variety of similarity matrices arising in NLP tasks. We demonstrate high accuracy of the approximated similarity matrices in tasks of more »
Authors:
; ; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10326696
Journal Name:
Proceedings of the AAAI Conference on Artificial Intelligence
ISSN:
2159-5399
5. In this paper, we propose a new class of operator factorization methods to discretize the integral fractional Laplacian \begin{document}$(- \Delta)^\frac{{ \alpha}}{{2}}$\end{document} for \begin{document}$\alpha \in (0, 2)$\end{document}. One main advantage is that our method can easily increase numerical accuracy by using high-degree Lagrange basis functions, but remain its scheme structure and computer implementation unchanged. Moreover, it results in a symmetric (multilevel) Toeplitz differentiation matrix, enabling efficient computation via the fast Fourier transforms. If constant or linear basis functions are used, our method has an accuracy of \begin{document}${\mathcal O}(h^2)$\end{document}, while \begin{document}${\mathcal O}(h^4)$\end{document} for quadratic basis functions with \begin{document}$h$\end{document} a small mesh size. This accuracy can be achieved for any \begin{document}$\alpha \in (0, 2)$\end{document} and can be further increased if higher-degree basis functions are chosen. Numerical experiments are provided to approximate the fractional Laplacian and solve the fractional Poisson problems. It shows that if the solution of fractional Poisson problem satisfies \begin{document}$u \in C^{m, l}(\bar{ \Omega})$\end{document} for \begin{document}$m \in {\mathbb N}$\end{document} and \begin{document}$0 < l < 1$\end{document}, our method has an accuracy of \begin{document}$more » for constant and linear basis functions, while \begin{document}$ {\mathcal O}(h^{\min\{m+l, \, 4\}}) \$\end{document} for quadratic basis functions. Additionally, our method can be readily applied to approximate the generalized fractional Laplacians with symmetric kernel function, and numerical study on the tempered fractional Poisson problem demonstrates its efficiency.