We simplify matrix computations for block matrices, especially useful for covariance and correlation matrices.
problem Complex computations for block matrices, especially for covariance and correlation matrices.
method Obtained a canonical representation for block matrices, facilitating computation of various matrix operations.
result Simplified computation of matrix operations for block matrices, particularly useful for covariance and correlation matrices.
Researchers developed a new Riemannian manifold for SPD matrix-valued optimal transport problems.
problem Optimal transport between SPD matrix-valued measures.
method Formulated as a generalized optimal transport problem with block SPD matrices, endowed with a novel Riemannian manifold structure.
result The novel Riemannian manifold allows solving SPD matrix-valued optimal transport problems using Riemannian optimization.
This paper solves matrix blind joint block diagonalization with noise.
problem Identifying the diagonalizer and block diagonal structure of matrices under noise.
method Bi-block diagonalization method.
result The method can identify the exact solution under certain conditions.
Introduces BMF for efficient matrix factorization of large data.
problem Efficiently factorizing large scale matrices with limited memory.
method Uses block matrix approach and factorization at a block level.
result Demonstrates faster convergence on large matrices.
We study the problem of computing the matrix exponential of a block triangular matrix in a peculiar way: Block column by block column, from left to right. The need for such an evaluation scheme arises naturally in the context of option pricing in polynomial diffusion models. In this setting a discretization process pro…
New test for latent block models to determine cluster numbers.
problem No statistical test for latent block models.
method Developed a goodness-of-fit test using random matrix theory.
result Demonstrated the effectiveness of the test method.
The paper reduces the complexity of financial market correlation matrices to a 2x2 matrix.
problem Reducing the complexity of financial market correlation matrices for easier analysis.
method Sectorial coarse graining followed by averaging over blocks of stocks.
result Averaging over blocks of stocks results in a reduced matrix with specific properties.
BlockEcho method improves imputation of block-wise missing data.
problem Block-wise missing data reduces interpolation capability and predictive power.
method Integrates Matrix Factorization (MF) within Generative Adversarial Networks (GAN) to retain long-distance inter-element relationships.
result Superior performance on public datasets across three domains, especially at higher missing rates.
Method estimates number of clusters in Block Markov Chain trajectories.
problem Challenges in choosing number of clusters for sequential data.
method Spectral embedding and density-based clustering.
result Asymptotically consistent method for estimating clusters.
Improved singular value approximation for convolutional layers.
problem Improving accuracy of singular value approximation for linear convolutional layers.
method Developed a new spectral density matrix method for singular value approximation with improved accuracy and reduced computational complexity.
result Obtained moderate improvement in singular value distribution compared to circular approximation.
Localized sketching improves matrix multiplication and ridge regression complexity.
problem Efficiently approximate matrix multiplication and ridge regression with limited data availability.
method Localized sketching matrices for block diagonal structure, reducing sample complexity.
result Localized sketching achieves sample complexity matching global sketching methods.
We present a method based on the orthogonal symmetric non-negative matrix tri-factorization of the normalized Laplacian matrix for community detection in complex networks. While the exact factorization of a given order may not exist and is NP hard to compute, we obtain an approximate factorization by solving an optimiz…
Paper proposes ABDR for convex subspace clustering with adaptive block diagonal representation.
problem Subspace clustering with block diagonal structure for noisy data.
method ABDR explicitly pursues block diagonality without sacrificing convexity, using a specially designed convex regularizer.
result Experimental results show ABDR outperforms state-of-the-arts.
This paper improves SVD for recommender systems using block-based matrix factorization.
problem Scalability and performance issues in recommender systems.
method Block-based Singular Value Decomposition (BMF) for matrix factorization.
result BMF paired with SVD enhances performance and scalability.
Advanced optimization algorithms such as Newton method and AdaGrad benefit from second order derivative or second order statistics to achieve better descent directions and faster convergence rates. At their heart, such algorithms need to compute the inverse or inverse square root of a matrix whose size is quadratic of …
New method clusters signed graphs using matrix power means.
problem Clustering signed graphs with positive and negative relations.
method Signed Power Mean Laplacian, defined as matrix power mean of normalized standard and signless Laplacians.
result Signed power mean Laplacian captures ground truth clusters under reasonable settings.
New adaptive methods improve deep learning performance.
problem Training deep networks efficiently and effectively.
method Block-diagonal matrix adaptation for gradient updates.
result Block-diagonal methods outperform adaptive diagonal methods and vanilla SGD.
Homogeneous links were introduced by Peter Cromwell, who proved that the projection surface of these links, that given by the Seifert algorithm, has minimal genus. Here we provide a different proof, with a geometric rather than combinatorial flavor. To do this, we first show a direct relation between the Seifert matrix…
Gaussian graphical models are widely utilized to infer and visualize networks of dependencies between continuous variables. However, inferring the graph is difficult when the sample size is small compared to the number of variables. To reduce the number of parameters to estimate in the model, we propose a non-asymptoti…
Paper solves a key problem in learning from high-dimensional covariance matrices.
problem Computing normalizing factors for Riemannian Gaussian distributions on high-dimensional covariance matrices.
method Equivalence with random matrix theory and log-normal matrix ensembles to approximate normalizing factors.
result Efficient approximation of normalizing factors with decreasing error as dimension increases.
New insights into Hessian structure of neural networks reveal two forces.
problem Understanding the Hessian structure of neural networks.
method Analyzing the static and dynamic forces, comparing limit distributions using random matrix theory.
result The Hessian structure arises from a combination of static and dynamic forces, with C being a primary driver. The paper identifies redundant columns in matrices for feature selection and clustering.
problem Identifying redundant columns in matrices for feature selection and clustering.
method Proves that after re-ordering columns, a matrix can be block-diagonalized revealing linearly dependent columns.
result Identifies redundant columns in matrices, aiding in feature selection and clustering.
The problem of outlier detection is extremely challenging in many domains such as text, in which the attribute values are typically non-negative, and most values are zero. In such cases, it often becomes difficult to separate the outliers from the natural variations in the patterns in the underlying data. In this paper…
Modular method simplifies curvature computation in neural nets.
problem Efficient computation of curvature matrices for training neural nets.
method Modular backpropagation for block-diagonal approximations.
result Compact notation and easy integration into machine learning libraries.
A common problem in large-scale data analysis is to approximate a matrix using a combination of specifically sampled rows and columns, known as CUR decomposition. Unfortunately, in many real-world environments, the ability to sample specific individual rows or columns of the matrix is limited by either system constrain…
Method selects number of communities in weighted networks.
problem Selecting the number of communities in weighted networks.
method Proposes a novel weighted DCSBM and uses a sequential testing framework with spectral clustering and matrix scaling.
result Method is consistent in estimating the true number of communities under mild conditions.
Nonnegative matrix factorization (NMF) has attracted much attention in the last decade as a dimension reduction method in many applications. Due to the explosion in the size of data, naturally the samples are collected and stored distributively in local computational nodes. Thus, there is a growing need to develop algo…
Proposes a new regularizer for semi-supervised learning on multilayer graphs.
problem Semi-supervised learning on multilayer graphs with labeled and unlabeled data.
method Generalized matrix mean regularizer and matrix-free numerical scheme.
result The regularizer outperforms state-of-the-art methods numerically.
Second-order methods for neural network optimization have several advantages over methods based on first-order gradient descent, including better scaling to large mini-batch sizes and fewer updates needed for convergence. But they are rarely applied to deep learning in practice because of high computational cost and th…
A new method for spectral positional encodings in directed graphs using Hermitian block Krylov subspaces.
problem Challenges in spectral positional encodings for directed graphs, including computational complexity and gauge invariance issues.
method Learnable spectral positional encodings of the form hθ(Aq)R, computed in a Hermitian block Krylov subspace from sparse matrix-vector products. result The method is gauge-invariant and converges to the exact eigendecomposition oracle as the depth grows.
This paper tackles fitting multilevel low rank matrices by addressing three problems.
problem Fitting a given matrix by an MLR matrix in the Frobenius norm.
method Factor fitting, rank allocation, and hierarchical partitioning.
result The proposed methods can fit a given matrix by an MLR matrix in the Frobenius norm.
New estimators reduce computation for Kendall's tau and conditional Kendall's tau matrices under structural assumptions.
problem Efficient estimation of Kendall's tau and conditional Kendall's tau matrices for large dimensions.
method Averaging pairwise estimates over blocks or conditional estimates, exploiting structural assumptions.
result Improved estimators with reduced computational cost and similar error level.
Recently it has become popular to learn sparse Gaussian graphical models (GGMs) by imposing l1 or group l1,2 penalties on the elements of the precision matrix. Thispenalized likelihood approach results in a tractable convex optimization problem. In this paper, we reinterpret these results as performing MAP estimation u…
Efficiently approximates Sparse PCA with significant speedups and minor error.
problem Sparse Principal Component Analysis (Sparse PCA) is NP-hard and computationally expensive.
method Approximates the covariance matrix with block-diagonal form, solves sub-problems in each block, and reconstructs the solution.
result Significant computational speedups with minor additive error.
We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the network can consistently recover hidden communities even when the order of the maximum expected degree is as small as $\l…
Two spectral algorithms for community detection in graphs with covariates are compared.
problem Detecting community structure in graphs with covariates.
method Two model-based spectral algorithms are presented and compared.
result The second algorithm often better estimates block assignments by accounting for vertex covariates.
A new method for state space partitioning in block particle filtering reduces bias and variance.
problem Overcoming the curse of dimensionality in non-linear, non-Gaussian state space estimation.
method Formulates state space partitioning as a clustering problem and uses spectral clustering with constraints.
result The proposed method effectively groups correlated state variables into smaller blocks, reducing bias and variance.
In this paper we consider a general matrix factorization model which covers a large class of existing models with many applications in areas such as machine learning and imaging sciences. To solve this possibly nonconvex, nonsmooth and non-Lipschitz problem, we develop a non-monotone alternating updating method based o…
New Bethe-Hessian method improves community detection in sparse networks.
problem Detect communities in sparse networks efficiently.
method Spectral clustering using the Bethe-Hessian matrix.
result Bethe-Hessian consistently estimates block number above Kesten-Stigum threshold.
New method for community detection in graphs faster than DCBM inference.
problem Efficiently detecting communities in graphs with heterogeneous node degrees.
method Reformulated constrained nonnegative matrix factorization for DCBM inference.
result Faster community detection (4 minutes for 100k nodes vs. DCBM's 10+ minutes).
A deep neural network is a hierarchical nonlinear model transforming input signals to output signals. Its input-output relation is considered to be stochastic, being described for a given input by a parameterized conditional probability distribution of outputs. The space of parameters consisting of weights and biases i…
Optimal spectral method found for inhomogeneous spiked Wigner model.
problem Structured noise in learning scenarios.
method Random matrix theory and spectral analysis.
result Optimal threshold for phase transition in block-structured Wigner model.
Study on signal-plus-noise decomposition in nonlinear spiked random matrices.
problem Nonlinear spiked random matrix models with rank-one signal and noise.
method Signal-plus-noise decomposition and phase transition analysis.
result Identified precise phase transitions in signal components at critical thresholds.
In this paper, we propose two new algorithms for transduction with Matrix Completion (MC) problem. The joint MC and prediction tasks are addressed simultaneously to enhance the accuracy, i.e., the label matrix is concatenated to the data matrix forming a stacked matrix. Assuming the data matrix is of low rank, we propo…
New method for directed graphs using learnable spectral positional encodings.
problem Challenges in magnetic Laplacians and unitary gauge invariance for directed graphs.
method Learnable spectral PEs of the form hθ(Aq)R, computed in Hermitian block Krylov subspace.
result Gauge-invariant and computationally efficient solution for directed graphs.
New method reduces linear regret in high-dimensional bandit problems.
problem Heavy spectral tails in streaming matrices lead to linear regret in sketch-based linear bandits.
method Dyadic Block Sketching, a multi-scale matrix sketching approach.
result Achieves sublinear regret bounds without prior knowledge of streaming matrix properties.
Variational inference improves neural network matrix factorization for stochastic blockmodels.
problem Improving predictive performance of neural network matrix factorization for stochastic blockmodels.
method Construct Bayesian neural networks and fit with variational inference.
result Variational inference can achieve equivalent performance to neural networks on Movielens data.
Study on determinants of unitary Brownian motion and their asymptotic laws.
problem Understanding determinants of unitary Brownian motion and their behavior over time.
method Using Stiefel fibration and skew-product decomposition of the Stiefel Brownian motion.
result Prove asymptotic laws for determinants of block entries of unitary Brownian motion.