A sparse decomposition of low rank symmetric positive semidefinite matrices

DOI10.1137/16M107760XMaRDI QIDQ5737757zbMATH OpenOpenAlexFDO

Authors Qin Li, Pengchuan Zhang, Thomas Y. Hou

Publication date 30 May 2017

Published in Multiscale Modeling & Simulation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.00702

zbMATH Keywords

intrinsic sparse mode decompositionjoint diagonalizationmatrix factorizationpivoted Cholesky decompositionprincipal component analysissparse PCA

Mathematics Subject Classification ID

Positive matrices and their generalizations; cones of matrices (15B48) Computational methods for sparse matrices (65F50)

Abstract: Suppose that $Ainmathbb{R}^{NimesN}$ is symmetric positive semidefinite with rank $KleN$. Our goal is to decompose $A$ into $K$ rank-one matrices $su{m}_{k=1}^K{g}_k{g}_k^T$ where the modes ${g_k}_{k=1}^K$ are required to be as sparse as possible. In contrast to eigen decomposition, these sparse modes are not required to be orthogonal. Such a problem arises in random field parametrization where $A$ is the covariance function and is intractable to solve in general. In this paper, we partition the indices from 1 to $N$ into several patches and propose to quantify the sparseness of a vector by the number of patches on which it is nonzero, which is called patch-wise sparseness. Our aim is to find the decomposition which minimizes the total patch-wise sparseness of the decomposed modes. We propose a domain-decomposition type method, called intrinsic sparse mode decomposition (ISMD), which follows the "local-modes-construction + patching-up" procedure. The key step in the ISMD is to construct local pieces of the intrinsic sparse modes by a joint diagonalization problem. Thereafter a pivoted Cholesky decomposition is utilized to glue these local pieces together. Optimal sparse decomposition, consistency with different domain decomposition and robustness to small perturbation are proved under the so called regular-sparse assumption (see Definition 1.2). We provide simulation results to show the efficiency and robustness of the ISMD. We also compare the ISMD to other existing methods, e.g., eigen decomposition, pivoted Cholesky decomposition and convex relaxation of sparse principal component analysis [25] and [40].

Recommendations

• Rank-Sparsity Incoherence for Matrix Decomposition
• Decomposition methods for sparse matrix nearness problems
• A sparsity for decomposing a symmetric matrix
• scientific article; zbMATH DE number 6142618
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

Cites work

• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• A multiscale finite element method for elliptic problems in composite materials and porous media
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
• Compressed modes for variational problems in mathematics and physics
• Deflation Techniques for an Implicitly Restarted Arnoldi Iteration
• Density matrix minimization with \({\ell}_1\) regularization
• Domain Decomposition Preconditioners for Multiscale Flows in High Contrast Media: Reduced Dimension Coarse Spaces
• Exploring the locally low dimensional structure in solving random elliptic PDEs
• scientific article; zbMATH DE number 3560401 (Why is no real title available?)
• scientific article; zbMATH DE number 1260614 (Why is no real title available?)
• scientific article; zbMATH DE number 3046994 (Why is no real title available?)
• Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
• Learning the parts of objects by non-negative matrix factorization
• Local polynomial chaos expansion for linear differential equations with high dimensional random inputs
• Localized bases of eigensubspaces and operator compression
• Mode decomposition methods for flows in high-contrast porous media. Global-local approach
• Multiscale finite element methods for high-contrast problems using local spectral basis functions
• Numerical Methods for Simultaneous Diagonalization
• On the Perturbation of Pseudo-Inverses, Projections and Linear Least Squares Problems
• Online learning for matrix factorization and sparse coding
• Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization
• Rank-Sparsity Incoherence for Matrix Decomposition
• Removing the cell resonance error in the multiscale finite element method via a Petrov-Galerkin formulation
• Robust principal component analysis?
• Sparse PCA: convex relaxations, algorithms and applications
• Wannier90: A tool for obtaining maximally-localised Wannier functions

Cited in

(13)

• Galerkin methods for stationary radiative transfer equations with uncertain coefficients
• Low rank approximation of the symmetric positive semidefinite matrix
• A decomposition method for positive semidefinite matrices and its application to recursive parameter estimation
• scientific article; zbMATH DE number 4178733 (Why is no real title available?)
• ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
• Low-rank/sparse-inverse decomposition via Woodbury
• Uniform regularity for linear kinetic equations with random input based on hypocoercivity
• Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices
• Sensitivity Analysis of Burgers' Equation with Shocks
• Exploring the locally low dimensional structure in solving random elliptic PDEs
• Numerical homogenization beyond scale separation
• Stochastic Galerkin methods for time-dependent radiative transfer equations with uncertain coefficients
• Sparse operator compression of higher-order elliptic operators with rough coefficients

Describes a project that uses

Uses Software

• PMA
• IRAM
• eigs

This page was built for publication: A sparse decomposition of low rank symmetric positive semidefinite matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5737757)