Zobrazeno 1 - 10
of 152
pro vyhledávání: '"Musco, Cameron"'
Autor:
Chen, Tyler, Keles, Feyza Duman, Halikias, Diana, Musco, Cameron, Musco, Christopher, Persson, David
We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an $n\times n$ matrix $\mathbf{A}$, accessible only though matrix-vector products with $\mathbf{A}$ and $\mathbf{A}^{\mathsf{T
Externí odkaz:
http://arxiv.org/abs/2407.04686
Autor:
Daneshvaramoli, Mohammadreza, Karisani, Helia, Lechowicz, Adam, Sun, Bo, Musco, Cameron, Hajiesmaili, Mohammad
In the online knapsack problem, the goal is to pack items arriving online with different values and weights into a capacity-limited knapsack to maximize the total value of the accepted items. We study \textit{learning-augmented} algorithms for this p
Externí odkaz:
http://arxiv.org/abs/2406.18752
There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any
Externí odkaz:
http://arxiv.org/abs/2405.18680
Autor:
Musco, Cameron, Sheth, Kshiteej
We present a sublinear time algorithm for computing a near optimal low-rank approximation to any positive semidefinite (PSD) Toeplitz matrix $T\in \mathbb{R}^{d\times d}$, given noisy access to its entries. In particular, given entrywise query access
Externí odkaz:
http://arxiv.org/abs/2404.13757
Autor:
Amsel, Noah, Chen, Tyler, Keles, Feyza Duman, Halikias, Diana, Musco, Cameron, Musco, Christopher
We study the problem of approximating a matrix $\mathbf{A}$ with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when $\mathbf{A}$ is accessed only by matrix-vector products. We describe a simple randomized algorithm that r
Externí odkaz:
http://arxiv.org/abs/2402.09379
In this work, we introduce a novel evaluation framework for generative models of graphs, emphasizing the importance of model-generated graph overlap (Chanpuriya et al., 2021) to ensure both accuracy and edge-diversity. We delineate a hierarchy of gra
Externí odkaz:
http://arxiv.org/abs/2312.03691
Autor:
Chanpuriya, Sudhanshu, Musco, Cameron
Algorithms for node clustering typically focus on finding homophilous structure in graphs. That is, they find sets of similar nodes with many edges within, rather than across, the clusters. However, graphs often also exhibit heterophilous structure,
Externí odkaz:
http://arxiv.org/abs/2308.06448
Structured kernel interpolation (SKI) accelerates Gaussian process (GP) inference by interpolating the kernel covariance function using a dense grid of inducing points, whose corresponding kernel matrix is highly structured and thus amenable to fast
Externí odkaz:
http://arxiv.org/abs/2305.14451
Autor:
Bhattacharjee, Rajarshi, Dexter, Gregory, Musco, Cameron, Ray, Archan, Sachdeva, Sushant, Woodruff, David P
Let $\mathbf S \in \mathbb R^{n \times n}$ satisfy $\|\mathbf 1-\mathbf S\|_2\le\epsilon n$, where $\mathbf 1$ is the all ones matrix and $\|\cdot\|_2$ is the spectral norm. It is well-known that there exists such an $\mathbf S$ with just $O(n/\epsil
Externí odkaz:
http://arxiv.org/abs/2305.05826
Krylov subspace methods are a ubiquitous tool for computing near-optimal rank $k$ approximations of large matrices. While "large block" Krylov methods with block size at least $k$ give the best known theoretical guarantees, block size one (a single v
Externí odkaz:
http://arxiv.org/abs/2305.02535