Spectral algorithm recovers clusters in hypergraph with high probability.
problem Exact recovery of clusters in hypergraph stochastic block model.
method Spectral algorithm based on adjacency matrix of hypergraph.
result Exact recovery with high probability for k = Θ ( n ) k=Θ(\sqrt{n}) k = Θ ( n ) clusters. Spectral flow connects manifold geometry to rigidity criteria.
problem Tackling rigidity of simply-connected closed manifolds.
method Spectral deformation flow and invariant-based approach.
result Spherical profile is the unique manifold-compatible asymptotic realization.
Optimizes ranking of top-k players from partial comparison data.
problem Identifying the top-k players from incomplete pairwise comparisons.
method Maximum Likelihood Estimator (MLE) and Spectral Method.
result MLE achieves optimal partial and exact recovery, while Spectral Method is sub-optimal.
Develops an ℓ_p theory for PCA and spectral clustering.
problem Lack of precise characterizations of PCA scores for low-dimensional embedding.
method An ℓ_p perturbation theory for PCA in Hilbert spaces, analyzing eigenvectors and Gram matrix.
result Optimal recovery results for Gaussian mixture and stochastic block models.
Study spectral estimators for multi-index models to recover low-dimensional signal subspaces.
problem Recovering low-dimensional signal subspaces in multi-index models.
method Spectral estimators for multi-index models.
result Precise asymptotic characterization of spectral methods' performance, revealing a phase transition for weak recovery.
New spectral tensor network algorithms solve continuous tensor problems.
problem Continuous tensor decomposition and orbit recovery problems over infinite groups.
method Leverage tensor networks to design spectral algorithms.
result Solve continuous multi-reference alignment over infinite SO(2) group.
New method for community detection in sparse directed SBMs with exact recovery guarantees.
problem Exact recovery in sparse directed SBMs, especially with growing communities.
method Two-stage procedure: neighborhood-smoothing followed by K K K -means clustering. result Exact recovery of all community labels with probability tending to one under mild sparsity and separation conditions.
Spectral methods improve signal recovery in mixed GLMs with precise asymptotics.
problem Estimating multiple signals from unlabeled observations in mixed GLMs.
method Developed exact asymptotics for spectral methods in a proportional regime.
result Optimized spectral method combined with a linear estimator minimizes estimation error.
Optimal spectral estimators and AMP combine for efficient weak recovery in orthogonally invariant GLMs.
problem Parameter estimation from generalized linear models with complex correlation structures.
method Spectral initialization and approximate message passing (AMP) algorithm.
result Established rigorous performance guarantees for spectral initialization and AMP.
New spectral clustering method handles discrete covariates for better community detection.
problem Community detection in networks with discrete covariates.
method Spectral algorithm that separates latent network structure from observed covariates.
result Achieves perfect clustering with high probability in large, sparse networks.
Spectral clustering for geometric graphs achieves strong consistency in community recovery.
problem Community recovery in dense geometric graphs.
method Spectral clustering algorithm using eigenvectors of adjacency matrix.
result Strong consistency in community recovery proved.
Spectral clustering achieves strong consistency in the stochastic block model under certain conditions.
problem Achieving strong consistency in spectral clustering for the stochastic block model.
method Entrywise analysis of the Fielder eigenvector of graph Laplacians.
result Spectral clustering achieves exact recovery of hidden communities under matching information-theoretic limits.
A new clustering method improves recovery guarantees by re-embedding data.
problem Improving recovery guarantees in clustering algorithms.
method Chaining four techniques: leapfrog distances, multidimensional scaling, spectral methods, and sum-of-norms clustering.
result Re-embedding data improves recovery guarantees of clustering.
Spectral methods achieve near-optimal performance in orthogonal and permutation group synchronization.
problem Recovering group elements from pairwise measurements in computer vision.
method Spectral methods applied with the leave-one-out technique.
result Near-optimal performance bounds for orthogonal and permutation group synchronization established.
Optimal low rank tensor recovery requires a minimum number of entries for accurate reconstruction.
problem Exact recovery of high order tensors of low rank from a subset of their entries.
method Riemannian optimization algorithm with initial value from a spectral method, leveraging tensor restricted isometry property and curvature of the manifold.
result Tensor of size n i m e s n i m e s ⋯ i m e s n n imes n imes \cdots imes n nim es nim es ⋯ im es n of ranks ( r , ⋯ , r ) (r,\cdots,r) ( r , ⋯ , r ) can be reconstructed with high probability from O ( ( r d + d n r ) log ( d ) ) O((r^d+dnr)\log(d)) O (( r d + d n r ) log ( d )) entries. In this paper, we develop an approach to recursively estimate the quadratic risk for matrix recovery problems regularized with spectral functions. Toward this end, in the spirit of the SURE theory, a key step is to compute the (weak) derivative and divergence of a solution with respect to the observations. As such a so…
Combines BTEM and T-PLS for accurate spectral recovery and calibration.
problem Calibrating pure spectra of minority components in mixtures without prior knowledge.
method Band target entropy minimization (BTEM) and target partial least squares (T-PLS).
result Estimated amounts from BTEM-T-PLS similar to MCR-ALS on simple mixtures, superior on complex ones.
Study spectral properties of sparse random graphs to recover latent vectors.
problem Recovering latent vectors in sparse random geometric graphs.
method Analyzes spectral concentration and uses orthogonal polynomial expansions, decoupling, and matrix concentration.
result Sharpens spectral norm bounds and proves exact recovery for Gaussian mixture models.
The study reveals the spectral structure of attention layers and its implications for generalization.
problem Understanding the spectral structure and generalization of trained attention layers.
method Empirical risk minimization in a single-head tied-attention layer, using random matrix theory, spin-glass theory, and approximate message passing.
result Exact high-dimensional characterization of training and test error, interpolation and recovery thresholds, and spectrum of the key and query matrices.
Spectral method for joint community detection and group synchronization.
problem Jointly detecting communities and synchronizing orthogonal groups in graphs.
method Spectral decomposition followed by CPQR factorization.
result Near-optimal guarantees for exact and stable recovery of cluster memberships and orthogonal transforms.
In recent years, spectral clustering has become a standard method for data analysis used in a broad range of applications. In this paper we propose a new class of algorithms for multiway spectral clustering based on optimization of a certain "contrast function" over the unit sphere. These algorithms, partly inspired by…
Improved spectral clustering guarantees for dynamic stochastic block models.
problem Analyzing Spectral Clustering in dynamic stochastic block models.
method Extending guarantees to sparse and smooth DSBM, linking sparsity and smoothness.
result Improved error bounds for consistent recovery in dynamic DSBM.
A new model for dynamic covariance recovery in neuroimaging data.
problem Estimating time-varying covariances in high-dimensional neuroimaging data.
method Nonconvex factorization into sparse spatial and smooth temporal components, combined with spectral initialization and gradient descent.
result The proposed method achieves linear convergence and superior performance compared to existing approaches.
Study optimal spectral estimator for semi-supervised node classification.
problem Semi-supervised node classification on CSBM with limited labels.
method Spectral estimator inspired by PCA, graph ridge regression, GCN.
result Achieves information-theoretical threshold for exact recovery.
Paper solves TRPCA problem for tensor data with new tensor nuclear norm.
problem Exact recovery of tensor low-rank and sparse components.
method Introduces tensor-tensor product and new tensor nuclear norm to solve TRPCA.
result The new tensor nuclear norm guarantees exact recovery of tensor data.
Improved spectral method recovers sparse vectors in random subspaces.
problem Recovering a sparse vector in a random subspace with sub-Gaussian entries.
method Improved spectral method with leave-one-out analysis.
result Spectral method recovers sparse vectors with high probability under certain conditions.
New method detects communities in complex hypergraphs, matching theoretical limits.
problem Detecting communities in non-uniform hypergraphs with varying hyperedge sizes.
method Developed a spectral theory for weighted non-backtracking operators on non-uniform hypergraphs.
result Achieved the Kesten-Stigum bound for weak recovery in a general class of non-uniform HSBMs.
Study spectral learning for odeco tensors, addressing initialization bottlenecks.
problem Recovering orthogonally decomposable tensors under noise.
method Investigates perturbation bounds, non-convex optimization, and initialization strategies.
result Initialization is the main bottleneck for efficient algorithms.
A new method resolves permutation issues in shuffled linear regression for large-scale applications.
problem Estimating latent features through linear transformation with unknown permutations.
method Spectral matching method to align spectral components of measurement and feature covariances.
result Achieves accurate estimates in shuffled LS and LASSO settings with sufficient samples.
New algorithm reduces hyperparameter search space using group sparsity.
problem Efficient hyperparameter selection in machine learning.
method Modifies Harmonica algorithm with group-sparse recovery and HyperBand.
result Improves over existing methods like Successive Halving and Random Search.
The paper explores the problem of \emph{spectral compressed sensing}, which aims to recover a spectrally sparse signal from a small random subset of its n n n time domain samples. The signal of interest is assumed to be a superposition of r r r multi-dimensional complex sinusoids, while the underlying frequencies can assum…
Flexible model captures varying scales in data clusters.
problem Real-world data often exhibits varying scales or intensities, violating the homogeneity assumption of classical Gaussian mixture models.
method Individual-heterogeneous sub-Gaussian mixture model with an efficient spectral method for exact recovery.
result The method provably achieves exact recovery of true cluster labels under mild separation conditions.
Muon spectral optimizer outperforms SGD in associative memory tasks.
problem Understanding the advantage of spectral optimizers in learning associative memory.
method Linear associative memory problem, Gaussian inputs and outputs, power law frequency distribution, thresholded gradient approximation.
result Muon significantly outperforms SGD in storage capacity and recovery rates.
Algorithm recovers sparse PCA support from incomplete data.
problem Sparse PCA with incomplete and noisy data.
method Semidefinite program (SDP) relaxation of non-convex l 1 l_1 l 1 -regularized PCA. result SDP enables exact recovery of true support of sparse leading eigenvector.
Develops a new method to recover large latent tree models efficiently.
problem Inference of large latent tree structures from terminal node observations.
method Spectral Top-Down Recovery (STDR) using Fiedler vector partitioning.
result Proves statistical consistency and sample complexity for accurate tree recovery.
Paper improves robust spectral clustering for noisy data.
problem Noisy data and heavy-tailed entries hinder traditional clustering methods.
method Robust spectral clustering with rank statistics for latent structure recovery.
result Provable recovery of latent block structure in large data matrices.
In this paper, we propose a new method for estimating the conditional risk-neutral density (RND) directly from a cross-section of put option bid-ask quotes. More precisely, we propose to view the RND recovery problem as an inverse problem. We first show that it is possible to define restricted put and call operators th…
The paper analyzes sparse PCA for incomplete data and proves support recovery conditions.
problem Support recovery in sparse PCA with non-random missing data.
method Semidefinite relaxation of the ℓ 1 \ell_1 ℓ 1 -regularized PCA problem. result Support of the sparse leading eigenvector can be recovered with high probability.
Study reveals efficient recovery of multi-modal signals via Bayesian methods and sequential learning.
problem Recovering multiple high-dimensional signals from correlated modalities.
method Bayesian Approximate Message Passing and Sequential Curriculum Learning.
result Sequential learning strategy optimally recovers weak signals in multi-modal settings.
New algorithm IAC recovers hidden communities in labeled SBM with optimal performance.
problem Recovering hidden communities in Labeled Stochastic Block Model with varying cluster sizes.
method IAC (Instance-Adaptive Clustering) algorithm, consisting of spectral clustering and iterative likelihood-based improvements.
result IAC achieves optimal performance matching instance-specific lower bounds in expectation and with high probability.
Efficient algorithms for low-rank bandits using subspace recovery.
problem Contextual bandits with low-rank reward matrices.
method Spectral methods for subspace recovery, reformulating as linear bandits.
result Nearly optimal policy evaluation and best policy identification, minimax guarantees for regret minimization.
The paper tackles HS target localization using robust PCA with dictionary-based approach.
problem Localized target detection in hyperspectral images.
method Formulates HS image as low-rank + dictionary sparse, develops recovery guarantees.
result Recovery guarantees and performance analysis on real HS datasets.
Sharp theory of neural network scaling laws for hierarchical targets.
problem Learning hierarchical multi-index models in neural networks.
method Sharp information-theoretic scaling laws derived for two-layer neural networks.
result Optimal rates achieved by a simple spectral estimator.
Neural node embeddings have recently emerged as a powerful representation for supervised learning tasks involving graph-structured data. We leverage this recent advance to develop a novel algorithm for unsupervised community discovery in graphs. Through extensive experimental studies on simulated and real-world data, w…
A hierarchical model shows how scaling laws emerge from sequential feature recovery.
problem Emergence of scaling laws from feature learning in multi-layer networks.
method Layer-wise spectral algorithm adapted to compositional structure, sequential feature detection.
result Sequential detection of latent features, leading to explicit power-law decay of prediction error.
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatori…
Phase retrieval requires at least d+o(d) measurements to recover signals with high probability.
problem Recovering signals from quadratic measurements with noisy data.
method Used Gaussian sensing vectors and spectral methods to analyze the minimum number of measurements needed.
result A sharp phase transition occurs at n = d+o(d), where a simple spectral estimator achieves positive correlation.
The question of how to determine the number of independent latent factors (topics) in mixture models such as Latent Dirichlet Allocation (LDA) is of great practical importance. In most applications, the exact number of topics is unknown, and depends on the application and the size of the data set. Bayesian nonparametri…