Nonnegative Matrix and Tensor Factorization

---
count: false
class: nord-dark, middle, center

# Nonnegative Matrix and Tensor Factorization: An Overview 📊✨

## Presented by Your Helpful Expert

### [Current Date]

---

### 1. Navigating the Data Deluge 🌊

-   **Modern Society's Challenge:** The increasing need to process large amounts of data.
-   **Key Data Class:** Nonnegative matrices and tensors are crucial in many application areas.
-   **The Problem:** These datasets are often considerably large, making processing and evaluation difficult and time-consuming.
-   **Our Solution:** Matrix and Tensor Factorization techniques provide efficient ways to approximate and simplify this data.

---

### 2. What is Nonnegative Matrix Factorization (NMF)? 🤔

-   **Definition:** NMF is an efficient technique to **approximate a large matrix containing only nonnegative elements as a product of two nonnegative matrices of significantly smaller size**.
  -   This technique is also known as "Nonnegative Matrix Approximation" or "Approximative Nonnegative Matrix Factorization".
-   **History:**
  -   The idea was published in 1994 as "Positive Matrix Factorization".
  -   Gained widespread attention after a 1999 _Nature_ article about NMF.
-   **Purpose:** To extract useful features from data, simplify complex data into meaningful patterns, and enable easier analysis and processing.

---

### 3. The NMF Problem Formulation 📝

-   **Informal Description:** Given a nonnegative matrix $Y$ (size $I \times T$), find two nonnegative matrices $A$ (size $I \times J$) and $X$ (size $J \times T$) such that their product $AX$ approximates $Y$.
  -   $J$ is usually much smaller than $I$ and $T$.
  -   **In general, it's an approximation:** $Y \approx AX$ (or $Y = AX + E$, where $E$ is the approximation error).
-   **Formal Definition:** Given $Y \in \mathbb{R+}^{I \times T}$ and a positive integer $J$, find $A \in \mathbb{R+}^{I \times J}$ and $X \in \mathbb{R+}^{J \times T}$ that minimize the functional:
  $$ f(A,X) = \frac{1}{2} \|Y - AX\|^2_F $$
  -   $\|M\|_F$ is the Frobenius norm, defined as $\sqrt{\sum^I \sum^T m^2(i,t) }$.
  -   Other measures like Kullback-Leibler divergence or Alpha/Beta-divergences can also be used.

---

### 4. Why Non-Negativity Matters? 💡

-   **Distinctive Property:** Unlike methods such as Singular Value Decomposition (SVD) or Principal Component Analysis (PCA), NMF **guarantees that the factors are nonnegative**.
-   **Interpretability:** This non-negativity allows the factorization to be viewed as an **additive combination of features**.
  -   Every column of $A$ can be interpreted as a basis feature, and columns of $AX$ are additive combinations of weighted basis features.
  -   This property helps in discovering **hidden structures** in data while preserving interpretability.
-   **Contrast with PCA/SVD:**
  -   PCA/SVD can produce negative elements in factors, making interpretation difficult, especially with nonnegative data like image pixel values or signal intensities.
  -   PCA allows linear combination of "eigenfaces," while NMF only allows **additive combinations** of basis images.

---

### 5. Diverse Applications of NMF 🎯

NMF is widely used in various fields due to its ability to extract meaningful, interpretable features.

-   **Document Classification & Text Mining:** Extracting key topics from document-term matrices, email classification, and clustering.
-   **Multi-way Data Analysis:** Processing complex, multi-dimensional datasets.
-   **Image Processing:** Feature extraction in facial recognition, object detection, image compression, and denoising.
-   **Spectral Data Analysis:** Identifying patterns in sound, medical signals, and chemical spectra.
-   **Computational Biology & Genomics:** Gene expression analysis, molecular pattern discovery, and class comparison.
-   **Neuroscience & EEG Data Analysis**.
-   **Separation of Sound Sources & Music Transcription**.
-   **Internet Distance Estimation in Networks**.
-   **Speech Denoising:** Removing non-stationary noise from speech signals.
-   **Recommendation Systems:** Collaborative filtering to identify latent factors influencing user-item interactions.
-   **Community Detection:** Estimating mixed memberships in social networks.
-   **Data Imputation:** Handling missing data in statistical analysis.
-   **Astronomy:** Dimension reduction and analysis of astrophysical signals.

---

### 6. NMF Algorithms: Multiplicative Updates (NUR) 🔄

-   **Popular Method:** Introduced by Lee and Seung (1999, 2001) due to its simplicity.
-   **Mechanism:** Iteratively adjusts elements of $W$ and $H$ based on the gradient of the loss function, ensuring non-negativity throughout.
-   **Update Rules (Squared Euclidean distance):**
  $$ W*{iq} \leftarrow W*{iq} \frac{(A H^T)_{iq} }{(W(H H^T))_{iq} } $$
    $$ H*{qj} \leftarrow H*{qj} \frac{(W^T A)_{qj} }{((W^T W)H)_{qj} } $$
  -   Note: Updates are element-wise, not matrix multiplication.
-   **Pros:** Easy to implement and computationally cheap.
-   **Cons:** Can be slow to converge, and division by zero must be prevented.

---

### 7. NMF Algorithms: Alternating Least Squares (ALS) / ANLS 🤝

-   **Approach:** Also known as Alternating Non-negativity Constrained Least Squares (ANLS).
-   **Mechanism:** Alternately optimizes $W$ and $H$ while keeping the other fixed.
  -   This breaks the complex NMF problem into simpler **Nonnegative Least Squares (NNLS)** subproblems.
  -   Example:
    -   Minimize $H \ge 0 : \|WH - A\|^2_F$ (for $H$)
    -   Minimize $W \ge 0 : \|H^T W^T - A^T\|^2_F$ (for $W$)
-   **NNLS Subproblems:** Each subproblem $\min_{x \ge 0} \|Ex - f\|^2$ can be solved using **active set methods**.
  -   **Karush-Kuhn-Tucker (KKT) Conditions:** These are conditions for an optimal solution in constrained optimization problems.
-   **Performance:** ANLS typically requires significantly fewer iterations and less computing time than multiplicative update rules for similar approximation error.

---

### 8. Other NMF Algorithms ⚙️

-   **Hierarchical Alternating Least Squares (HALS):**
  -   Minimizes a set of local cost functions by approximating rank-one tensors.
  -   Algorithms include Simple HALS (Algorithm 3) and FAST HALS (Algorithm 4).
  -   Can be formulated based on Alpha- and Beta-divergences as well.
-   **Block Principal Pivoting (BPP):**
  -   An active-set-like method to compute NMF.
  -   Reduces the problem to a matrix problem, allowing NMF algorithms to be used.
-   **Convex NMF:**
  -   Restricts factors to convex combinations of input data, improving data representation quality and leading to sparser, more orthogonal factors.
-   **Sparse NMF (SNMF):**
  -   Introduces L1-norm regularization on the coefficient matrix $H$ to enforce sparsity.
  -   Aims to improve interpretability and performance in clustering by forcing data points to be represented by a small number of basis vectors.
  -   Experimental results show SNMF gives much better and consistent solutions for clustering problems compared to K-means.

---

### 9. Memory-Efficient Frank-Wolfe (MERIT) for Separable NMF 💾🚀

-   **The Challenge:** Many convex optimization-based separable NMF algorithms, like Self-Dictionary Multiple Measurement Vectors (SD-MMV), face a significant memory challenge, scaling quadratically with problem size ($O(N^2)$). This limits their application to big data.
-   **MERIT's Contribution:** Proposes a **memory-efficient algorithm** for convex SD-MMV that capitalizes on the special update rules of the Frank-Wolfe (FW) algorithm.
-   **Key Advantage:** It achieves a **linear memory cost** that grows as $O(KN)$, where $K$ is the latent factor dimension (much smaller than $N$).
-   **Robustness:** A smoothed group sparsity regularizer is proposed to improve robustness to noise while maintaining low memory footprint.
-   **Performance:** MERIT exhibits competitive performance compared to state-of-the-art baselines like SPA and FastGradient in tasks such as topic modeling and community detection, especially in terms of memory efficiency for large datasets.

---

### 10. Nonnegative Tensor Factorization (NTF) 🧊

-   **Concept:** Generalizes Nonnegative Matrix Factorization (NMF) for data that are tensors of third or higher order. Matrices are considered second-order tensors.
-   **Applications:** Essential for multi-way data analysis problems.
-   **Problem Definition:** Often formulated as **CANDECOMP / PARAFAC (Canonical Decomposition / Parallel Factor Decomposition)**.
  -   Given an N-th order tensor $Y \in \mathbb{R}^{I_1 \times I_2 \times \dots \times I_N}_{+}$ and an integer $J$, factorize $Y$ into a set of N nonnegative component matrices $A^{(n)} \in \mathbb{R}^{I_n \times J}_{+}$:
    $$ Y = \hat{Y} + E = \sum\_{j=1}^J a^{(1)}\_j \circ a^{(2)}\_j \circ \dots \circ a^{(N)}\_j + E $$
        where $\circ$ denotes the outer product, and $E$ is the approximation error.
-   **NTF Algorithms:**
  -   **Alpha NTF:** Multiplicative updates based on the Alpha-divergence.
  -   **Beta NTF:** Multiplicative updates based on the Beta-divergence.
  -   **HALS NTF:** Hierarchical Alternating Least Squares algorithms for tensors, typically using squared Euclidean distance, but can also be based on Alpha- and Beta-divergences.

---

### 11. Key Challenges & Limitations 🚧

-   **Non-Convex Objective:** NMF optimization involves a non-convex objective function, meaning algorithms can get stuck in **local minima**, potentially leading to suboptimal results. A provably optimal algorithm is unlikely due to NP-hard generalization to k-means.
-   **Sensitivity to Initialization:** NMF's convergence and solution quality can be sensitive to the initial values of the factorized matrices ($W$ and $H$).
-   **Determining the Number of Components ($k$ or $J$):** Selecting the appropriate number of components is crucial and challenging, often relying on heuristics, cross-validation, or domain knowledge.
-   **Overfitting:** NMF can be susceptible to overfitting, especially with a large number of components relative to the data size. Regularization can help.
-   **Computational Complexity:** For large datasets, NMF can be computationally intensive, requiring efficient algorithms and parallelization.
-   **Sparsity and Missing Data:** Handling sparse data or data with missing values can be challenging, often requiring imputation or specialized NMF variants.

---

### 12. Best Practices for Effective NMF/NTF Usage ✨

To effectively harness the power of NMF/NTF:

-   **Understand Your Data:** Be aware of its non-negativity, sparsity, and domain-specific meaning.
-   **Preprocess Your Data:** Clean and preprocess data to remove noise, outliers, and irrelevant features.
-   **Choose the Right Number of Components ($r$/$J$):** Use techniques like the elbow method, cross-validation, or domain knowledge.
-   **Select the Initialization Method:** Experiment with different methods (e.g., 'random', 'nndsvd') as it impacts convergence and solution quality.
-   **Monitor Convergence:** Check if the reconstruction error stabilizes over iterations.
-   **Consider Regularization/Sparsity Constraints:** Add if your data benefits from them to prevent overfitting.
-   **Interpretability Matters:** Pay attention to interpreting the basis ($W$) and coefficient ($H$) matrices using visualization and domain knowledge.
-   **Handle Missing Data:** Impute missing values before applying NMF, aligning with data characteristics.
-   **Choose the Right Algorithm:** Understand the strengths and weaknesses of different algorithms (e.g., multiplicative updates, ALS) for your problem and data size.
-   **Experiment and Iterate:** Don't be afraid to try different settings; finding optimal configuration may take attempts.
-   **Documentation and Reproducibility:** Keep detailed records of experiments for reproducibility and future reference.

---

### 13. Conclusion & Future Work ✅

-   **NMF/NTF are Powerful Tools:** Valuable and versatile techniques for data analysis, machine learning, and scientific research.
-   **Key Strengths:** Uncovering latent structures, dimensionality reduction, and extracting meaningful, interpretable representations from nonnegative data.
-   **Unique Property:** The non-negativity constraint aligns well with data exhibiting additive combinations, making it ideal for interpretable features.
-   **Continuous Improvement:** Ongoing research focuses on algorithmic enhancements, scalability for large datasets, online updates, collective factorization, and addressing theoretical challenges.
-   **Parallelization:** Future work should emphasize parallelizing algorithms to process large real-world problems on modern computing systems.

---

### Q&A ❓

Your questions are welcome!

---

### References 📚

-   Excerpts from "Algorithms for Nonnegative Tensor Factorization" (Markus Flatz, Technical Report 2013-05, November 2013, University of Salzburg).
-   Excerpts from "CF Recommender system Based on Ontology and Nonnegative Matrix Factorization (NMF) - arXiv" (Sajida Mhammedi et al.).
-   Excerpts from "Low-rank approximation - KASAI Laboratory | WASEDA University".
-   Excerpts from "Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach - arXiv" (Tri Nguyen et al.).
-   Excerpts from "NNLS and NMF - SPSC @ TU Graz" (Christian Knoll, Jakob Mangelberger, January 30, 2012).
-   Excerpts from "Non-Negative Matrix Factorization - GeeksforGeeks".
-   Excerpts from "Non-Negative Matrix Factorization Explained & How To Guide - Spot Intelligence" (Neri Van Otten, Sep 8, 2023).
-   Excerpts from "Non-negative matrix factorization - Wikipedia".
-   Excerpts from "Sparse Nonnegative Matrix Factorization for Clustering - College of Computing" (Jingu Kim and Haesun Park).

## (Individual source numbers [i] correspond to the provided source excerpts for specific statements)