Technical Summary: Heterogeneous Matrix Factorization (HMF)

Problem Statement

In many statistical applications, data is collected from multiple related but heterogeneous sources (e.g., IoT edge devices operating under varying conditions). These datasets exhibit both shared features (common knowledge across sources) and unique features (idiosyncratic characteristics specific to each source). The fundamental challenge is to decouple these shared and unique factors from observations.

Existing approaches face significant limitations:

• Heuristic Methods: Algorithms like JIVE (Joint and Individual Variation Explained) often fail to strictly enforce orthogonality between shared and unique components, leading to imperfect separation and limited fidelity in shared component estimates.
• Lack of Guarantees: Many existing methods rely on heuristic algorithms without strong theoretical convergence guarantees.
• Scalability and Flexibility: While personalized PCA (perPCA) offers convergence guarantees, it is restricted to symmetric covariance matrices and cannot easily handle asymmetric or incomplete observation settings.
• Distributed Constraints: Distributing existing algorithms to handle source-specific differences is often arduous.

The paper addresses the need for an extensible, distributed algorithm that separates shared and unique factors with provable convergence guarantees, capable of handling asymmetric and incomplete data.

Methodology

1. Linear Model Formulation

The authors propose Heterogeneous Matrix Factorization (HMF). Given $N$ observation matrices $\{M^{(i)}\}_{i=1}^N$ from $N$ sources, the data generation model is defined as:
$$M^{(i)} = U^*_g V^{(i),*T}_g + U^*_{(i),l} V^{(i),*T}_{(i),l} + E^*_{(i)}$$
Where:

• $U^*_g V^{(i),*T}_g$ represents the shared low-rank components (common across all sources).
• $U^*_{(i),l} V^{(i),*T}_{(i),l}$ represents the unique low-rank components (specific to source $i$).
• $E^*_{(i)}$ is noise.

A critical constraint is imposed to ensure the shared and unique features span different subspaces:
$$U^{*T}_g U^*_{(i),l} = 0, \quad \forall i \in [N]$$

The objective is to solve a constrained optimization problem minimizing the sum of regularized empirical risks (e.g., squared error) subject to the orthogonality constraint.

2. The HMF Algorithm

The core innovation of HMF is the exploitation of an invariance property in the objective function to handle the orthogonality constraint without projecting onto a non-convex feasible set.

• Invariance Property: The objective function remains invariant under a specific transformation $\phi_R$ involving a matrix $R$. By choosing $R = (U^T_g U_g)^{-1} U^T_g U_{(i),l}$, the algorithm can automatically correct the variables $V^{(i)}_g$ and $U_{(i),l}$ to satisfy the orthogonality constraint $U^T_g U_{(i),l} = 0$ without altering the loss value.
• Iterative Procedure:
  1. Correction Step: In each iteration, variables are corrected using the transformation $\phi_R$ to ensure feasibility (orthogonality).
  2. Gradient Descent: Standard gradient descent is applied to update the variables and minimize the regularized objective.
  3. Distributed Nature: The algorithm is intrinsically distributed. Each node $i$ computes local updates and sends the shared factor $U_g$ to a central server, which averages them and broadcasts the result back.

3. Extension to Nonlinear Models (HAE)

The framework is extended to Heterogeneous Auto-Encoders (HAE). Instead of linear embeddings, the model uses:

• A shared encoder ($NetU_g$) and $N$ unique encoders ($NetU_{(i),l}$).
• A shared decoder ($NetV$).
• A "group orthogonalization" constraint is applied to the folded outputs of the encoders to maintain the orthogonality of shared and unique nonlinear embeddings.

Key Contributions

1. Novel Framework: Introduction of HMF, a generic framework for separating shared and unique factors in heterogeneous data under orthogonality constraints.
2. Theoretical Guarantees:
   • Convergence: The paper proves that under the square error (SE) loss, HMF converges linearly to an optimal solution, provided the initial optimality gap is within a certain basin of attraction and the step size is appropriate.
   • Statistical Error Bound: The authors establish an upper bound on the statistical error between the optimal solution and the ground truth. To the best of their knowledge, this is the first such bound proven in the context of heterogeneous matrix factorization. This bound depends on the "misalignment" parameter $\theta$; higher misalignment (more distinct subspaces) leads to tighter error bounds.
   • General Loss: For general Lipschitz continuous loss functions, the algorithm is proven to converge to KKT points.
3. Handling Incomplete Data: Unlike previous methods (e.g., perPCA), HMF is designed to handle asymmetric and incomplete observation settings (matrix completion).
4. Distributed Implementation: The algorithm is naturally suited for distributed computing environments, making it scalable for edge devices.

Experimental Results

The authors validate HMF through synthetic data and three real-world case studies:

1. Synthetic Data:

   • HMF demonstrated linear convergence of errors, consistent with theoretical predictions.
   • In matrix completion tasks with up to 50% missing entries, HMF achieved significantly lower subspace errors compared to baselines (JIVE, RJIVE, perPCA).

2. Video Segmentation:

   • Applied to a surveillance video with 40% missing pixels.
   • HMF successfully separated stationary background (shared) and moving vehicles (unique).
   • Metrics: HMF achieved a background MSE of 0.001 and PSNR of 29.8, outperforming JIVE, RJIVE, and perPCA, which had significantly higher errors and lower PSNRs.

3. Stock Market Analysis:

   • Analyzed daily stock prices of 214 stocks to identify market-specific patterns.
   • The "heterogeneity index" derived from unique features successfully correlated with major historical market crashes (e.g., Dot-com bubble, 9/11, 2008 Financial Crisis), showing peaks during periods of market instability.

4. Recommender Systems (MovieLens-100k):

   • Linear Model (HMF): Outperformed standard matrix completion and AutoSVD++ in RMSE (0.977 vs 0.981).
   • Nonlinear Model (HAE): By incorporating genre-specific encoders, HAE achieved the lowest RMSE (0.8800) among all tested methods, including GraphRec and Sparse FC.
   • Visualization: t-SNE plots showed that HAE embeddings formed clear clusters based on movie genres, whereas standard auto-encoders did not, demonstrating the model's ability to learn meaningful heterogeneous structures.

Significance and Claims

The paper claims that HMF provides a flexible formulation and a first-order algorithm with provable convergence guarantees for heterogeneous matrix factorization, a gap left by previous heuristic approaches.

• Robustness: The authors provide a statistical error bound in the context of heterogeneous matrix factorization, noting this as a first to the best of their knowledge.
• Versatility: It bridges the gap between linear factorization and deep learning (auto-encoders) while maintaining orthogonality constraints.
• Practicality: The algorithm is computationally efficient ($O(n_1 n_2 (r_1 + r_2))$ per iteration) and naturally distributed, making it suitable for modern edge computing and IoT scenarios.

The authors modestly note that while the theoretical convergence relies on a specific initial optimality gap, empirical results suggest the algorithm performs well with small random initializations, relaxing the practical need for a "good" initial point. Future work is suggested to address unknown ranks (overparameterization) and further relax initialization conditions.