Nonnegative Matrix Factorization

✍ Scribed by Nicolas Gillis

• Publisher: SIAM - Society for Industrial and Applied Mathematics
• Year: 2020
• Tongue: English
• Leaves: 369
• Category: Library

✦ Synopsis

Nonnegative matrix factorization (NMF) in its modern form has become a standard tool in the analysis of high-dimensional data sets. This book provides a comprehensive and up-to-date account of the most important aspects of the NMF problem and is the first to detail its theoretical aspects, including geometric interpretation, nonnegative rank, complexity, and uniqueness. It explains why understanding these theoretical insights is key to using this computational tool effectively and meaningfully. Nonnegative Matrix Factorization is accessible to a wide audience and is ideal for anyone interested in the workings of NMF. It discusses some new results on the nonnegative rank and the identifiability of NMF and makes available MATLAB codes for readers to run the numerical examples presented in the book. Graduate students starting to work on NMF and researchers interested in better understanding the NMF problem and how they can use it will find this book useful. It can be used in advanced undergraduate and graduate-level courses on numerical linear algebra and on advanced topics in numerical linear algebra and requires only a basic knowledge of linear algebra and optimization

✦ Table of Contents

Contents
Preface
Notation
List of Figures
List of Tables
Chapter 1. Introduction
1.1 Linear dimensionality reduction techniques for data
analysis
1.2 Problem definition
1.3 Four applications of NMF in data analysis
1.4 History
1.5 Take-home messages
Part I. Exact factorizations
Chapter 2. Exact NMF
2.1 Geometric interpretation
2.2 Restricted Exact NMF
2.3 Computational complexity of RE-NMF and Exact NMF
2.4 Take-home messages
Chapter 3. Nonnegative rank
3.1 Some properties of the nonnegative rank
3.2 The nonnegative rank under perturbations
3.3 Generic values of the nonnegative rank
3.4 Lower bounds on the nonnegative rank
3.5 Upper bounds for the nonnegative rank
3.6 Lower bounds on extended formulations via thenonnegative rank
3.7 Link with communication complexity
3.8 Other applications of the nonnegative rank
3.9 Take-home messages
Chapter 4. Identifiability
4.1 Case rank(X) ≤ 2
4.2 Exact NMF with r = rank(X)
4.3 Regularized Exact NMF
4.4 Take-home messages
Part II. Approximate factorizations
Chapter 5. NMF models
5.1 Error measures
5.2 Model-order selection
5.3 Regularizations
5.4 NMF variants
5.5 Models related to NMF
5.6 Take-home messages
Chapter 6. Computational complexity of NMF
6.1 Frobenius norm
6.2 Kullback–Leibler divergence
6.3 Infinity norm
6.4 Weighted Frobenius norm
6.5 Componentwise l_1 norm
6.6 Other NMF models
6.7 Take-home messages
Chapter 7. Near-separable NMF
7.1 Context and applications
7.2 Preliminaries
7.3 Idealized algorithm
7.4 Greedy/sequential algorithms
7.5 Heuristic algorithms
7.6 Convex-optimization-based algorithms
7.7 Summary of provably robust near-separable NMF algorithms
7.8 Separable tri-symNMF
7.9 Further readings
7.10 Take-home messages
Chapter 8. Iterative algorithms for NMF
8.1 Preliminaries
8.2 The multiplicative updates
8.3 Algorithms for the Frobenius norm
8.4 Number of inner iterations and acceleration
8.5 Stopping criteria
8.6 Initialization
8.7 Alternative algorithmic approaches
8.8 Further readings
8.9 Online resources
8.10 Take-home messages
Chapter 9. Applications
9.1 Beware of scaling ambiguity
9.2 Should your data set be approximately of low rank?
9.3 Self-modeling curve resolution
9.4 Gene expression analysis
9.5 Recommender systems and collaborative filtering
9.6 Other applications
9.7 Take-home messages
Bibliography
[15]
[37]
[57]
[77]
[95]
[115]
[135]
[155]
[173]
[191]
[210]
[230]
[249]
[270]
[289]
[308]
[326]
[344]
[363]
[384]
[404]
[424]
[445]
[466]
[485]
[504]
Index
cde
fghi
jklm
n
opqr
s
tuvwyz