Nonnegative Matrix and Tensor Factorizations : Applications to Exploratory Multi-way Data Analysis and Blind Source Separation

by Andrzej Cichocki (Riken Brain Science Institute ); Rafal Zdunek (Wroclaw University of Technology ); Anh Huy Phan (Riken Brain Science Institute); Shun-ichi Amari (Riken Brain Science Institute )

• ISBN13: 9780470747285
• ISBN10: 0470747285
• Format: eBook
• Copyright: 2009-07-01
• Publisher: Wiley

Summary

This book provides a broad survey of models and efficient algorithms for Nonnegative Matrix Factorization (NMF). This includes NMFrs"s various extensions and modifications, especially Nonnegative Tensor Factorizations (NTF) and Nonnegative Tucker Decompositions (NTD). NMF/NTF and their extensions are increasingly used as tools in signal and image processing, and data analysis, having garnered interest due to their capability to provide new insights and relevant information about the complex latent relationships in experimental data sets. It is suggested that NMF can provide meaningful components with physical interpretations; for example, in bioinformatics, NMF and its extensions have been successfully applied to gene expression, sequence analysis, the functional characterization of genes, clustering and text mining. As such, the authors focus on the algorithms that are most useful in practice, looking at the fastest, most robust, and suitable for large-scale models. Key features: Acts as a single source reference guide to NMF, collating information that is widely dispersed in current literature, including the authorsrs" own recently developed techniques in the subject area. Uses generalized cost functions such as Bregman, Alpha and Beta divergences, to present practical implementations of several types of robust algorithms, in particular Multiplicative, Alternating Least Squares, Projected Gradient and Quasi Newton algorithms. Provides a comparative analysis of the different methods in order to identify approximation error and complexity. Includes pseudo codes and optimized MATLABreg; source codes for almost all algorithms presented in the book. The increasing interest in nonnegative matrix and tensor factorizations, as well as decompositions and sparse representation of data, will ensure that this book is essential reading for engineers, scientists, researchers, industry practitioners and graduate students across signal and image processing; neuroscience; data mining and data analysis; computer science; bioinformatics; speech processing; biomedical engineering; and multimedia.

Table of Contents

Preface

Acknowledgments

Glossary of Symbols and Abbreviations

Introduction - Problem Statements and Models

Blind Source Separation and Linear Generalized Component Analysis

Matrix Factorization Models with Nonnegativity and Sparsity Constraints

Why Nonnegativity and Sparsity Constraints?

Basic NMF Model

Symmetric NMF

Semi-Orthogonal NMF

Semi-NMF and Nonnegative Factorization of Arbitrary Matrix

Three-factor NMF

NMF with Offset (Affine NMF)

Multi-layer NMF

Simultaneous NMF

Projective and Convex NMF

Kernel NMF

Convolutive NMF

Overlapping NMF

Basic Approaches to Estimate Parameters of Standard NMF

Large-scale NMF

Non-uniqueness of NMF and Techniques to Alleviate the Ambiguity Problem

Initialization of NMF

Stopping Criteria

Tensor Properties and Basis of Tensor Algebra

Tensors (Multi-way Arrays) - Preliminaries

Subarrays, Tubes and Slices

Unfolding - Matricization

Vectorization

Outer, Kronecker, Khatri-Rao and Hadamard Products

Mode-n Multiplication of Tensor by Matrix and Tensor by Vector, Contracted Tensor Product

Special Forms of Tensors

Tensor Decompositions and Factorizations

Why Multi-way Array Decompositions and Factorizations?

PARAFAC and Nonnegative Tensor Factorization

NTF1 Model

NTF2 Model

Individual Differences in Scaling (INDSCAL) and Implicit Slice Canonical Decomposition Model (IMCAND)

Shifted PARAFAC and Convolutive NTF

Nonnegative Tucker Decompositions

Block Component Decompositions

Block-Oriented Decompositions

PARATUCK2 and DEDICOM Models

Hierarchical Tensor Decomposition

Discussion and Conclusions

Similarity Measures and Generalized Divergences

Error-induced Distance and Robust Regression Techniques

Robust Estimation

Csiszár Divergences

Bregman Divergence

Bregman Matrix Divergences

Alpha-Divergences

Asymmetric Alpha-Divergences

Symmetric Alpha-Divergences

Beta-Divergences

Gamma-Divergences

Divergences Derived from Tsallis and Rényi Entropy

Concluding Remarks

Multiplicative Iterative Algorithms for NMF with Sparsity Constraints

Extended ISRA and EMML Algorithms: Regularization and Sparsity

Multiplicative NMF Algorithms Based on the Squared Euclidean Distance

Multiplicative NMF Algorithms Based on Kullback-Leibler I-Divergence

Multiplicative Algorithms Based on Alpha-Divergence

Multiplicative Alpha NMF Algorithm

Generalized Multiplicative Alpha NMF Algorithms

Alternating SMART: Simultaneous Multiplicative Algebraic Reconstruction Technique

Alpha SMART Algorithm

Generalized SMART Algorithms

Multiplicative NMF Algorithms Based on Beta-Divergence

Multiplicative Beta NMF Algorithm

Multiplicative Algorithm Based on the Itakura-Saito Distance

Generalized Multiplicative Beta Algorithm for NMF

Algorithms for Semi-orthogonal NMF and Orthogonal Three-Factor NMF

Multiplicative Algorithms for Affine NMF

Multiplicative Algorithms for Convolutive NMF

Multiplicative Algorithm for Convolutive NMF Based on Alpha-Divergence

Multiplicative Algorithm for Convolutive NMF Based on Beta-Divergence

Efficient Implementation of CNMF Algorithm

Simulation Examples for Standard NMF

Examples for Affine NMF

Music Analysis and Decomposition Using Convolutive NMF

Discussion and Conclusions

Alternating Least Squares and Related Algorithms for NMF and SCA Problems

Standard ALS Algorithm

Multiple Linear Regression - Vectorized Version of ALS Update Formulas

Weighted ALS

Methods for Improving Performance and Convergence Speed of ALS Algorithms

ALS Algorithm for Very Large-scale NMF

ALS Algorithm with Line-Search

Acceleration of ALS Algorithm via Simple Regularization

ALS Algorithm with Flexible and Generalized Regularization Terms

ALS with Tikhonov Type Regularization Terms

ALS Algorithms with Sparsity Control and Decorrelation

Combined Generalized Regularized ALS Algorithms

Wang-Hancewicz Modified ALS Algorithm

Implementation of Regularized ALS Algorithms for NMF

HALS Algorithm and its Extensions

Projected Gradient Local Hierarchical Alternating Least Squares (HALS) Algorithm

Extensions and Implementations of the HALS Algorithm

Fast HALS NMF Algorithm for Large-scale Problems

HALS NMF Algorithm with Sparsity, Smoothness and Uncorrelatedness Constraints

HALS Algorithm for Sparse Component Analysis and Flexible Component Analysis

Simplified HALS Algorithm for Distributed and Multi-task Compressed Sensing

Generalized HALS-CS Algorithm

Generalized HALS Algorithms Using Alpha-Divergence

Generalized HALS Algorithms Using Beta-Divergence

Simulation Results

Underdetermined Blind Source Separation Examples

NMF with Sparseness, Orthogonality and Smoothness Constraints

Simulations for Large-scale NMF

Illustrative Examples for Compressed Sensing

Discussion and Conclusions

Projected Gradient Algorithms

Oblique Projected Landweber (OPL) Method

Lin's Projected Gradient (LPG) Algorithm with Armijo Rule

Barzilai-Borwein Gradient Projection for Sparse Reconstruction (GPSR-BB)

Projected Sequential Subspace Optimization (PSESOP)

Interior Point Gradient (IPG) Algorithm

Interior Point Newton (IPN) Algorithm

Regularized Minimal Residual Norm Steepest Descent Algorithm (RMRNSD)

Sequential Coordinate-Wise Algorithm (SCWA)

Simulations

Discussions

Quasi-Newton Algorithms for Nonnegative Matrix Factorization

Projected Quasi-Newton Optimization

Projected Quasi-Newton for Frobenius Norm

Projected Quasi-Newton for Alpha-Divergence

Projected Quasi-Newton for Beta-Divergence

Practical Implementation

Gradient Projection Conjugate Gradient

FNMA algorithm

NMF with Quadratic Programming

Nonlinear Programming

Quadratic Programming

Trust-region Subproblem

Updates for A

Hybrid Updates

Numerical Results

Discussions

Multi-Way Array (Tensor) Factorizations and Decompositions

Learning Rules for the Extended Three-way NTF1 Problem

Basic Approaches for the Extended NTF1 Model

ALS Algorithms for NTF1

Multiplicative Alpha and Beta Algorithms for the NTF1 Model

Multi-layer NTF1 Strategy

Algorithms for Three-way Standard and Super Symmetric Nonnegative Tensor Factorization

Multiplicative NTF Algorithms Based on Alpha- and Beta-Divergences

Simple Alternative Approaches for NTF and SSNTF

Nonnegative Tensor Factorizations for Higher-Order Arrays

Alpha NTF Algorithm

Beta NTF Algorithm

Fast HALS NTF Algorithm Using Squared Euclidean Distance

Generalized HALS NTF Algorithms Using Alpha- and Beta-Divergences

Tensor Factorization with Additional Constraints

Algorithms for Nonnegative and Semi-Nonnegative Tucker Decompositions

Higher Order SVD (HOSVD) and Higher Order Orthogonal Iteration (HOOI) Algorithms

ALS Algorithm for Nonnegative Tucker Decomposition

HOSVD, HOOI and ALS Algorithms as Initialization Tools for Nonnegative Tensor Decomposition

Multiplicative Alpha Algorithms for Nonnegative Tucker Decomposition

Beta NTD Algorithm

Local ALS Algorithms for Nonnegative TUCKER Decompositions

Semi-Nonnegative Tucker Decomposition

Nonnegative Block-Oriented Decomposition

Multiplicative Algorithms for NBOD

Multi-level Nonnegative Tensor Decomposition - High Accuracy Compression and Approximation

Simulations and Illustrative Examples

Experiments for Nonnegative Tensor Factorizations

Experiments for Nonnegative Tucker Decomposition

Experiments for Nonnegative Block-Oriented Decomposition

Multi-Way Analysis of High Density Array EEG - Classification of Event Related Potentials

Application of Tensor Decompositions in Brain Computer Interface - Classification of Motor Imagery Tasks

Image and Video Applications

Discussion and Conclusions

Selected Applications

Clustering

Semi-Binary NMF

NMF vs. Spectral Clustering

Clustering with Convex NMF

Application of NMF to Text Mining

Email Surveillance

Classification

Musical Instrument Classification

Image Classification

Spectroscopy

Raman Spectroscopy

Fluorescence Spectroscopy

Hyperspectral Imaging

Chemical Shift Imaging

Application of NMF for Analyzing Microarray Data

Gene Expression Classification

Analysis of Time Course Microarray Data

References

Index

Table of Contents provided by Publisher. All Rights Reserved.