product iamge

Nonnegative matrix and tensor factorizations

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book provides a broad survey of models and efficient algorithms for Nonnegative Matrix Factorization (NMF). This includes NMF’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 authors’ 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 MATLAB 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.

Author(s): Andrzej Cichocki, Rafal Zdunek, Anh Huy Phan, Shun-ichi Amari
Publisher: Wiley
Year: 2009

Language: English
Pages: 501

NONNEGATIVE MATRIX AND TENSOR FACTORIZATIONS: APPLICATIONS TO EXPLORATORY MULTI-WAY DATA ANALYSIS AND BLIND SOURCE SEPARATION......Page 5
Contents......Page 7
Preface......Page 13
Acknowledgments......Page 17
Glossary of Symbols and Abbreviations......Page 19
1 Introduction -
Problem Statements and Models......Page 25
1.1 Blind Source Separation and Linear Generalized Component Analysis......Page 26
1.2.1 Why Nonnegativity and Sparsity Constraints?......Page 31
1.2.2 Basic NMF Model......Page 32
1.2.3 Symmetric NMF......Page 33
1.2.6 Three-factor NMF......Page 34
1.2.7 NMF with Offset (Affine NMF)......Page 37
1.2.9 Simultaneous NMF......Page 38
1.2.10 Projective and Convex NMF......Page 39
1.2.12 Convolutive NMF......Page 40
1.2.13 Overlapping NMF......Page 41
1.3 Basic Approaches to Estimate Parameters of Standard NMF......Page 42
1.3.1 Large-scale NMF......Page 45
1.3.2 Non-uniqueness of NMF and Techniques to Alleviate the Ambiguity Problem......Page 46
1.3.3 Initialization of NMF......Page 48
1.3.4 Stopping Criteria......Page 49
1.4.1 Tensors (Multi-way Arrays) – Preliminaries......Page 50
1.4.2 Subarrays, Tubes and Slices......Page 51
1.4.3 Unfolding – Matricization......Page 52
1.4.4 Vectorization......Page 55
1.4.5 Outer, Kronecker, Khatri-Rao and Hadamard Products......Page 56
1.4.6 Mode-n Multiplication of Tensor by Matrix and Tensor by Vector, Contracted Tensor Product......Page 58
1.4.7 Special Forms of Tensors......Page 62
1.5 Tensor Decompositions and Factorizations......Page 63
1.5.1 Why Multi-way Array Decompositions and Factorizations?......Page 64
1.5.2 PARAFAC and Nonnegative Tensor Factorization......Page 66
1.5.3 NTF1 Model......Page 71
1.5.4 NTF2 Model......Page 73
1.5.5 Individual Differences in Scaling (INDSCAL) and Implicit Slice Canonical Decomposition Model (IMCAND)......Page 76
1.5.6 Shifted PARAFAC and Convolutive NTF......Page 77
1.5.7 Nonnegative Tucker Decompositions......Page 79
1.5.8 Block Component Decompositions......Page 83
1.5.9 Block-Oriented Decompositions......Page 86
1.5.10 PARATUCK2 and DEDICOM Models......Page 87
1.5.11 Hierarchical Tensor Decomposition......Page 89
Appendix 1.A: Uniqueness Conditions for Three-way Tensor Factorizations......Page 90
Appendix 1.B: Singular Value Decomposition (SVD) and Principal Component Analysis (PCA) with Sparsity and/or Nonnegativity Constraints......Page 91
1.B.1 Standard SVD and PCA......Page 92
1.B.2 Sparse PCA......Page 94
Appendix 1.C: Determining a True Number of Components......Page 95
Appendix 1.D: Nonnegative Rank Factorization Using Wedderborn Theorem – Estimation of the Number of Components......Page 98
References......Page 99
2 Similarity Measures and Generalized Divergences......Page 105
2.1 Error-induced Distance and Robust Regression Techniques......Page 106
2.2 Robust Estimation......Page 108
2.3 Csiszár Divergences......Page 114
2.4 Bregman Divergence......Page 120
2.4.1 Bregman Matrix Divergences......Page 127
2.5.1 Asymmetric Alpha-Divergences......Page 128
2.5.2 Symmetric Alpha-Divergences......Page 134
2.6 Beta-Divergences......Page 136
2.7 Gamma-Divergences......Page 140
2.8 Divergences Derived from Tsallis and Rényi Entropy......Page 142
2.8.1 Concluding Remarks......Page 143
2.A.1 Space of Probability Distributions......Page 144
2.A.2 Geometry of Space of Positive Measures......Page 147
Appendix 2.B: Probability Density Functions for Various Distributions......Page 149
References......Page 151
3 Multiplicative Iterative Algorithms for NMF with Sparsity Constraints......Page 155
3.1.1 Multiplicative NMF Algorithms Based on the Squared Euclidean Distance......Page 156
3.1.2 Multiplicative NMF Algorithms Based on Kullback-Leibler I-Divergence......Page 163
3.2.1 Multiplicative Alpha NMF Algorithm......Page 167
3.2.2 Generalized Multiplicative Alpha NMF Algorithms......Page 171
3.3.1 Alpha SMART Algorithm......Page 172
3.3.2 Generalized SMART Algorithms......Page 174
3.4.1 Multiplicative Beta NMF Algorithm......Page 175
3.4.3 Generalized Multiplicative Beta Algorithm for NMF......Page 180
3.5 Algorithms for Semi-orthogonal NMF and Orthogonal Three-Factor NMF......Page 181
3.6 Multiplicative Algorithms for Affine NMF......Page 183
3.7 Multiplicative Algorithms for Convolutive NMF......Page 184
3.7.2 Multiplicative Algorithm for Convolutive NMF Based on Beta-Divergence......Page 186
3.7.3 Efficient Implementation of CNMF Algorithm......Page 189
3.8 Simulation Examples for Standard NMF......Page 190
3.9 Examples for Affine NMF......Page 194
3.10 Music Analysis and Decomposition Using Convolutive NMF......Page 200
3.11 Discussion and Conclusions......Page 208
3.A.1 Random Block-wise Processing Approach – Large-scale NMF......Page 211
3.B.1 Signal-to-Interference-Ratio - SIR......Page 212
3.B.2 Peak Signal-to-Noise-Ratio (PSNR)......Page 214
Appendix 3.C: Convergence Analysis of the Multiplicative Alpha NMF Algorithm......Page 215
3.D.1 Alpha Algorithm......Page 217
3.D.2 SMART Algorithm......Page 219
3.D.3 ISRA Algorithm for NMF......Page 221
3.E.1 Multi-layer NMF......Page 222
References......Page 223
4.1 Standard ALS Algorithm......Page 227
4.1.2 Weighted ALS......Page 230
4.2.1 ALS Algorithm for Very Large-scale NMF......Page 231
4.2.3 Acceleration of ALS Algorithm via Simple Regularization......Page 232
4.3 ALS Algorithm with Flexible and Generalized Regularization Terms......Page 233
4.3.1 ALS with Tikhonov Type Regularization Terms......Page 234
4.3.2 ALS Algorithms with Sparsity Control and Decorrelation......Page 235
4.4 Combined Generalized Regularized ALS Algorithms......Page 236
4.6 Implementation of Regularized ALS Algorithms for NMF......Page 237
4.7.1 Projected Gradient Local Hierarchical Alternating Least Squares (HALS) Algorithm......Page 238
4.7.2 Extensions and Implementations of the HALS Algorithm......Page 240
4.7.3 Fast HALS NMF Algorithm for Large-scale Problems......Page 241
4.7.4 HALS NMF Algorithm with Sparsity, Smoothness and Uncorrelatedness Constraints......Page 244
4.7.5 HALS Algorithm for Sparse Component Analysis and Flexible Component Analysis......Page 246
4.7.6 Simplified HALS Algorithm for Distributed and Multi-task Compressed Sensing......Page 251
4.7.7 Generalized HALS-CS Algorithm......Page 255
4.7.8 Generalized HALS Algorithms Using Alpha-Divergence......Page 257
4.7.9 Generalized HALS Algorithms Using Beta-Divergence......Page 258
4.8.1 Underdetermined Blind Source Separation Examples......Page 260
4.8.2 NMF with Sparseness, Orthogonality and Smoothness Constraints......Page 261
4.8.3 Simulations for Large-scale NMF......Page 263
4.8.4 Illustrative Examples for Compressed Sensing......Page 265
4.9 Discussion and Conclusions......Page 273
Appendix 4.A: MATLAB Source Code for ALS Algorithm......Page 276
Appendix 4.B: MATLAB Source Code for Regularized ALS Algorithms......Page 277
Appendix 4.C: MATLAB Source Code for Mixed ALS-HALS Algorithms......Page 280
Appendix 4.D: MATLAB Source Code for HALS CS Algorithm......Page 283
Appendix 4.E: Additional MATLAB Functions......Page 285
References......Page 288
5 Projected Gradient Algorithms......Page 291
5.1 Oblique Projected Landweber (OPL) Method......Page 292
5.2 Lin’s Projected Gradient (LPG) Algorithm with Armijo Rule......Page 294
5.3 Barzilai-Borwein Gradient Projection for Sparse Reconstruction (GPSR-BB)......Page 295
5.4 Projected Sequential Subspace Optimization (PSESOP)......Page 297
5.5 Interior Point Gradient (IPG) Algorithm......Page 299
5.6 Interior Point Newton (IPN) Algorithm......Page 300
5.7 Regularized Minimal Residual Norm Steepest Descent Algorithm (RMRNSD)......Page 303
5.8 Sequential Coordinate-Wise Algorithm (SCWA)......Page 305
5.9 Simulations......Page 307
5.10 Discussions......Page 313
Appendix 5.A: Stopping Criteria......Page 314
Appendix 5.B: MATLAB Source Code for Lin’s PG Algorithm......Page 316
References......Page 317
6 Quasi-Newton Algorithms for Nonnegative Matrix Factorization......Page 319
6.1.1 Projected Quasi-Newton for Frobenius Norm......Page 320
6.1.2 Projected Quasi-Newton for Alpha-Divergence......Page 322
6.1.3 Projected Quasi-Newton for Beta-Divergence......Page 327
6.2 Gradient Projection Conjugate Gradient......Page 329
6.3 FNMA algorithm......Page 332
6.4 NMF with Quadratic Programming......Page 334
6.4.1 Nonlinear Programming......Page 335
6.4.2 Quadratic Programming......Page 336
6.4.3 Trust-region Subproblem......Page 338
6.4.4 Updates for A......Page 340
6.5 Hybrid Updates......Page 342
6.6 Numerical Results......Page 343
6.7 Discussions......Page 347
Appendix 6.A: Gradient and Hessian of Cost Functions......Page 348
Appendix 6.B: MATLAB Source Codes......Page 349
References......Page 357
7.1 Learning Rules for the Extended Three-way NTF1 Problem......Page 361
7.1.1 Basic Approaches for the Extended NTF1 Model......Page 362
7.1.2 ALS Algorithms for NTF1......Page 364
7.1.3 Multiplicative Alpha and Beta Algorithms for the NTF1 Model......Page 365
7.1.4 Multi-layer NTF1 Strategy......Page 367
7.2 Algorithms for Three-way Standard and Super Symmetric Nonnegative Tensor Factorization......Page 368
7.2.1 Multiplicative NTF Algorithms Based on Alpha- and Beta-Divergences......Page 369
7.2.2 Simple Alternative Approaches for NTF and SSNTF......Page 374
7.3 Nonnegative Tensor Factorizations for Higher-Order Arrays......Page 375
7.3.1 Alpha NTF Algorithm......Page 377
7.3.3 Fast HALS NTF Algorithm Using Squared Euclidean Distance......Page 379
7.3.4 Generalized HALS NTF Algorithms Using Alpha- and Beta-Divergences......Page 382
7.3.5 Tensor Factorization with Additional Constraints......Page 384
7.4 Algorithms for Nonnegative and Semi-Nonnegative Tucker Decompositions......Page 385
7.4.1 Higher Order SVD (HOSVD) and Higher Order Orthogonal Iteration (HOOI) Algorithms......Page 386
7.4.2 ALS Algorithm for Nonnegative Tucker Decomposition......Page 389
7.4.4 Multiplicative Alpha Algorithms for Nonnegative Tucker Decomposition......Page 390
7.4.6 Local ALS Algorithms for Nonnegative TUCKER Decompositions......Page 394
7.4.7 Semi-Nonnegative Tucker Decomposition......Page 398
7.5 Nonnegative Block-Oriented Decomposition......Page 399
7.5.1 Multiplicative Algorithms for NBOD......Page 400
7.6 Multi-level Nonnegative Tensor Decomposition - High Accuracy Compression and Approximation......Page 401
7.7.1 Experiments for Nonnegative Tensor Factorizations......Page 402
7.7.2 Experiments for Nonnegative Tucker Decomposition......Page 408
7.7.3 Experiments for Nonnegative Block-Oriented Decomposition......Page 416
7.7.4 Multi-Way Analysis of High Density Array EEG – Classification of Event Related Potentials......Page 419
7.7.5 Application of Tensor Decomposition in Brain Computer Interface – Classification of Motor Imagery Tasks......Page 428
7.7.6 Image and Video Applications......Page 433
7.8 Discussion and Conclusions......Page 436
Appendix 7.A: Evaluation of Interactions and Relationships Among Hidden Components for NTD Model......Page 439
Appendix 7.B: Computation of a Reference Tensor......Page 440
Appendix 7.C: Trilinear and Direct Trilinear Decompositions for Efficient Initialization......Page 442
Appendix 7.D: MATLAB Source Code for Alpha NTD Algorithm......Page 444
Appendix 7.E: MATLAB Source Code for Beta NTD Algorithm......Page 445
Appendix 7.F: MATLAB Source Code for HALS NTD Algorithm......Page 447
Appendix 7.G: MATLAB Source Code for ALS NTF1 Algorithm......Page 449
Appendix 7.H: MATLAB Source Code for ISRA BOD Algorithm......Page 450
Appendix 7.I: Additional MATLAB functions......Page 451
References......Page 453
8.1 Clustering......Page 457
8.1.1 Semi-Binary NMF......Page 458
8.1.2 NMF vs. Spectral Clustering......Page 459
8.1.3 Clustering with Convex NMF......Page 460
8.1.4 Application of NMF to Text Mining......Page 462
8.1.5 Email Surveillance......Page 464
8.2.1 Musical Instrument Classification......Page 466
8.2.2 Image Classification......Page 467
8.3.1 Raman Spectroscopy......Page 471
8.3.2 Fluorescence Spectroscopy......Page 473
8.3.3 Hyperspectral Imaging......Page 474
8.3.4 Chemical Shift Imaging......Page 476
8.4.1 Gene Expression Classification......Page 479
8.4.2 Analysis of Time Course Microarray Data......Page 483
References......Page 491
Index......Page 497