Matrix Decomposition on Graphs: A Functional View

• URL: http://arxiv.org/abs/2102.03233v1
• Date: Fri, 5 Feb 2021 15:28:11 GMT
• Title: Matrix Decomposition on Graphs: A Functional View
• Abstract summary: We propose a functional view of matrix decomposition problems on graphs. Our framework is based on the key idea that using a reduced basis to represent functions on the product space is sufficient to recover a low rank matrix approximation.
• Score: 36.85782408336389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a functional view of matrix decomposition problems on graphs such as geometric matrix completion and graph regularized dimensionality reduction. Our unifying framework is based on the key idea that using a reduced basis to represent functions on the product space is sufficient to recover a low rank matrix approximation even from a sparse signal. We validate our framework on several real and synthetic benchmarks (for both problems) where it either outperforms state of the art or achieves competitive results at a fraction of the computational effort of prior work.

Related papers

• Graph-Based Correlation Matrix Generation: A Convex Optimization Approach [0.0]
  This work addresses the generation of theoretical correlation matrices with prescribed sparsity patterns associated to graph structures.<n>We propose a novel convex optimization framework in which an initial matrix is projected onto an elliptope under a positive semidefiniteness constraint.
  arXiv  Detail & Related papers  (2026-07-24T15:54:23Z)
• Graph-Regularized Low-Rank Matrix Completion by Variable Projection [0.0]
  Graph-Regularized RTRMC (GR-RTRMC) exploits the inherent relationships between rows and columns of the matrix.<n>We aim to improve the accuracy and robustness of matrix completion, particularly in scenarios where the underlying data exhibits strong correlations between rows or columns.
  arXiv  Detail & Related papers  (2026-07-10T15:57:02Z)
• Taxonomy of reduction matrices for Graph Coarsening [14.662574002430794]
  Graph coarsening aims to diminish the size of a graph to lighten its memory footprint.<n>Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrix.<n>We show that, for a fixed coarsening represented by a fixed lifting matrix, the RSA can be further reduced simply by modifying the reduction matrix.
  arXiv  Detail & Related papers  (2025-06-13T12:55:03Z)
• Computational Efficient Informative Nonignorable Matrix Completion: A Row- and Column-Wise Matrix U-Statistic Pseudo-Likelihood Approach [2.2306682526405868]
  We establish a unified framework to deal with the high dimensional matrix completion problem. We derive a row- and column-wise matrix U-statistics type loss function, with the nuclear norm for regularization. A singular value proximal gradient algorithm is developed to solve the proposed optimization problem.
  arXiv  Detail & Related papers  (2025-04-05T01:41:53Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Semi-Supervised Clustering via Dynamic Graph Structure Learning [12.687613487964088]
  Most existing semi-supervised graph-based clustering methods exploit the supervisory information by refining the affinity matrix or constraining the low-dimensional representations of data points. We propose a novel dynamic graph learning method for semi-supervised graph clustering.
  arXiv  Detail & Related papers  (2022-09-06T14:05:31Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Graph-based Neural Acceleration for Nonnegative Matrix Factorization [0.0]
  We describe a graph-based neural acceleration technique for nonnegative matrix factorization. We train a graph neural network that interleaves bipartite self-attention layers with updates based on the alternating direction method of multipliers. Our evaluation on synthetic and two real-world datasets shows that we attain substantial acceleration, even though we only train in an unsupervised fashion on smaller synthetic instances.
  arXiv  Detail & Related papers  (2022-02-01T07:52:01Z)
• Matrix Completion with Hierarchical Graph Side Information [39.00971122472004]
  We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering. We conduct extensive experiments on synthetic and real-world datasets to corroborate our theoretical results.
  arXiv  Detail & Related papers  (2022-01-02T03:47:41Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Geometric Matrix Completion: A Functional View [35.58521417084282]
  We propose a novel regularization inspired from the functional map literature that is more interpretable and theoretically sound. On synthetic tasks with strong underlying geometric structure, our framework outperforms state of the art by a huge margin. On real datasets, we achieve state-of-the-art results at a fraction of the computational effort of previous methods.
  arXiv  Detail & Related papers  (2020-09-29T23:23:04Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.