PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Low Rank Models

Madeleine Udell, Corinne Horn, Reza Zadeh, Stephen Boyd

arXiv:1410.0342v4stat.MLcs.LGmath.OC

TL;DR

The paper addresses low-rank approximation for heterogeneous, incomplete data where conventional PCA is limited to numerical values and cross-type errors require careful comparison. It introduces generalized low rank models with data-type-specific losses, factor regularization, and scalable alternating-minimization algorithms. The framework unifies established methods and supports shared embeddings, imputation, denoising, clustering, and anomaly analysis, with heterogeneous losses outperforming quadratically regularized PCA when large data blocks are censored.

  • Problem

    Low-rank analysis must accommodate heterogeneous values and missing entries while comparing approximation errors across data types.

  • Method

    GLRMs approximate arbitrary data sets as products of low-dimensional factors using data-type-appropriate losses, factor regularization, and parallel alternating-minimization algorithms.

  • Results

    The framework encompasses established low-rank methods and heterogeneous-loss GLRMs perform much better than quadratically regularized PCA when a large data block is censored.

  • Takeaways & Limitations

    A shared low-dimensional representation supports compressing, denoising, imputing, clustering, and identifying anomalous examples or features across heterogeneous data.

  • Takeaways & Limitations

    Choosing denoising holdout sizes is not well understood beyond Gaussian noise and depends on data aspect ratio and noise type.

Abstract

from arXiv · show

Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types. This framework encompasses many well known techniques in data analysis, such as nonnegative matrix factorization, matrix completion, sparse and robust PCA, $k$-means, $k$-SVD, and maximum margin matrix factorization. The method handles heterogeneous data sets, and leads to coherent schemes for compressing, denoising, and imputing missing entries across all data types simultaneously. It also admits a number of interesting interpretations of the low rank factors, which allow clustering of examples or of features. We propose several parallel algorithms for fitting generalized low rank models, and describe implementations and numerical results.

1 Introduction

The paper generalizes low-rank modeling beyond numerical tables to heterogeneous, incomplete data, supporting exploratory analyses through shared low-dimensional embeddings. It unifies numerous existing techniques and develops scalable fitting methods for these broadly defined models.

  • Motivation: Heterogeneous tables may contain numerical, Boolean, ordinal, categorical, and missing values, complicating exploratory analysis.Relevant analyses include visualization, clustering, imputation, and anomaly identification.
  • Motivation: The approach embeds both examples and features in one low-dimensional vector space for plotting, clustering, imputing missing entries, and identifying anomalies.
  • Generalized low rank models: GLRMs approximate arbitrary data sets with two low-dimensional factors, using data-type-appropriate losses and regularization such as sparsity or nonnegativity.The resulting factorization retains a low-dimensional embedding of the data.
  • Generalized low rank models: The framework recovers formulations for nonnegative matrix factorization, matrix completion, sparse and robust PCA, k-means, k-SVD, and maximum margin matrix factorization.
  • Algorithms and theory: The paper develops alternating-minimization algorithms and parallel variants for losses and regularizers that may be smooth or nonsmooth, finite or infinite valued, and arbitrarily domain-constrained.It also derives a quadratically regularized PCA solution, rules out local nonglobal minima there, and gives special-case global-solution certificates.

2 PCA and quadratically regularized PCA

PCA represents numerical data with a low-rank factorization, while quadratic regularization shrinks singular values and bounds the solution set. Alternating minimization extends the solution strategy and supports interpretable, low-dimensional representations for examples and missing or noisy entries.

  • PCA: PCA seeks a best rank-k approximation by minimizing squared Frobenius error, with the rank constraint represented as Z = XY.The factors have dimensions X ∈ R^{m×k} and Y ∈ R^{k×n}.
  • PCA: The factor rows xi embed examples in k dimensions, while columns yj map compressed features back to the original feature space.This factorization compresses n original features into k < n new features.
  • Quadratically regularized PCA: Quadratic regularization adds penalties on X and Y; γ = 0 recovers PCA, while γ > 0 soft-thresholds singular values by γ.The regularized solution set is bounded and remains nonunique up to orthogonal transformations.
  • Solution methods: PCA has an analytical SVD solution, whereas alternating minimization repeatedly minimizes over X and Y with the other factor fixed.Each iteration is nonincreasing in objective value, and for γ > 0 the iterates are bounded.
  • Solution methods: Alternating minimization can fail from certain initializations, but every stable stationary point is a solution and the objective converges to its optimal value in practice.Initialization orthogonal to a top-k right singular vector prevents convergence to the global solution in exact arithmetic.
  • Interpretations and applications: The factorization supports archetypical example representations, clustering in a complete low-dimensional space, denoising observed entries, and imputing missing entries.The reconstructed value xiyj estimates missing entries and denoises observed values.

3 Generalized regularization

Generalized regularization extends PCA by imposing structure on low-dimensional factors, allowing one framework to represent diverse models and support parallel alternating optimization.

  • Generalized regularization: Regularized PCA adds arbitrary row and column penalties to low-rank factorization, including nonconvex regularizers.Infinite-valued regularizers can enforce constraints such as nonnegativity.
  • Examples: Varying the regularizers recovers models including nonnegative matrix factorization, sparse PCA, clustering, and bounded-factor matrix completion.Different regularizers can also be combined to impose properties such as simultaneous sparsity and nonnegativity.
  • Solution methods: Alternating minimization updates the two factors in parallel, solving convex or tractable subproblems when regularizers permit.The method is not guaranteed to reach the global minimum because the overall problem is generally nonconvex.
  • Examples: Regularizers can encode cluster assignments or geometric structure, including one-hot assignments and ray-based nonnegative factorizations.With one-hot row factors, each data vector is assigned to one of k clusters.
  • Examples: Regularized PCA can combine supervised and unsupervised learning in a single optimization problem.The first row of Y uses supervised-regression regularization, while the remaining rows use regularized-PCA regularization.

4 Generalized loss functions

Generalized low rank models replace PCA’s squared-error loss with data-appropriate losses, covering robust, asymmetric, relative-scale, and probabilistic approximations.

  • Generalized loss functions: A generalized low rank model minimizes data-specific losses Lij together with regularization on low-dimensional factors.Squared loss recovers regularized PCA, while the loss can depend on each observed data value.
  • Solution methods: Alternating minimization finds local minima, while stochastic proximal-gradient variants provide scalable access through subgradient or proximal interfaces.These interfaces allow the method to generalize to nearly any loss function and regularizer.
  • Robust models: A rank-constrained generalized-loss formulation recovers a robust PCA estimator using sparse error and nuclear-norm regularization.The equivalent formulation separates observations into a sparse corruption component and a low-rank component.
  • Robust models: Replacing squared loss with ℓ1 or Huber loss yields robust PCA formulations that tolerate large outliers and small Gaussian perturbations.The Huber formulation is equivalent to a robust decomposition involving Gaussian and Laplacian error components.
  • Relative-scale models: Relative-scale losses support approximations whose errors are measured proportionally rather than absolutely.An objective below 0.10mn produces a low-rank matrix averaging within 10% of the original entries.
  • Exponential-family models: β-divergence unifies quadratic, KL-divergence, and Itakura–Saito losses through limiting parameter choices.β = 2 gives quadratic loss, β → 1 gives KL divergence, and β → 0 gives Itakura–Saito loss.

5 Loss functions for abstract data types

GLRM extends low-rank approximation beyond numerical matrices by pairing data types with suitable loss functions. The resulting representations support imputation, denoising, compression, and feature or example embeddings across heterogeneous data.

  • GLRM models heterogeneous tables by assigning each feature a discrete or continuous set and each observed value a type-appropriate loss.The loss measures the error of representing a feature value with a real-valued low-rank estimate.
  • The generalized objective factorizes the data with X and Y while adding row- and feature-specific regularizers.With convex losses and regularizers, the problem is bi-convex and separable across samples and features, enabling alternating minimization.
  • Hinge, logistic, ordinal hinge, and Poisson losses specialize GLRM to Boolean, ordinal, and count-valued data.Logistic loss yields logistic PCA, while Poisson loss corresponds to the exponential-family model for Poisson data.
  • Ordinal modeling can encode levels as integers, but a learned ordinal loss can relax the assumption that every level increment is equally costly.This flexibility allows the model to learn unequal relationships between ordinal labels.
  • GLRM converts abstract feature spaces into low-dimensional real-valued vectors that can be plotted, clustered, or used by machine-learning algorithms.The columns of Y similarly embed features as combinations of archetypical features.

6 Multi-dimensional loss functions

Multi-dimensional generalized low rank models represent complex feature values with block embeddings and losses tailored to structured data types. The framework covers categorical, ordinal, permutation, ranking, and partially observed ranking data, while connecting categorical modeling to multiclass classification.

  • Multi-dimensional generalized low rank models: Block-dependent losses and embeddings extend generalized low rank models to categorical values, permutations, distributions, and rankings.Each feature can have its own embedding dimension and loss, with matrix-valued feature factors.
  • Categorical PCA: Categorical PCA uses multiclass-classification losses, including one-vs-all and nonseparable alternatives such as Crammer-Singer.Only one-vs-all is separable across classes, so other categorical losses are not equivalent to fitting separate Boolean features.
  • Categorical PCA: Nonseparable categorical losses combine classes by their maximum rather than their sum and tend to outperform one-vs-all as classes and examples increase.The cited comparison reports similar performance on small data sets but stronger performance from sophisticated nonseparable losses at larger scale.
  • Ordinal PCA: A larger embedding dimension lets ordinal PCA learn nonuniform relationships between ordinal levels from the data.With quadratic regularization, optimizing feature factors corresponds to training one SVM per ordinal threshold, while optimizing example factors places examples between separating hyperplanes.
  • Permutation and ranking PCA: Permutation PCA uses a loss whose minimizer sorts the predicted scores, yielding a low-rank approximation of tables of permutations.Ranking PCA generalizes this idea by penalizing pairwise deviations, and partially observed rankings can be handled through observed comparisons.
  • Numerical example: The heterogeneous-data example fits a low-rank model to 3,132,796 ACS responses across 23 demographic and economic questions.The learned feature space groups intuitively similar states and identifies correlations among hours worked, weeks worked, and education.

7 Fitting low rank models

Fitting generalized low rank models is generally computationally difficult, so the paper develops alternating and gradient-based local methods with parallel implementations and selected convergence or optimality guarantees. Experiments illustrate global convergence in regularized PCA, initialization-dependent outcomes in nonnegative factorization, and improved results from SVD initialization.

  • Computational difficulty: Exact global optimization is NP-hard for several special cases, including k-means, nonnegative matrix factorization, weighted PCA, and matrix completion.The paper therefore distinguishes efficiently fitted models with small objective values from globally optimal solutions.
  • Optimization algorithms: Alternating minimization updates example and feature factors separately, while lazy gradient, proximal-gradient, and stochastic variants trade per-iteration speed against iteration count.The updates can be executed in parallel over examples and features.
  • Proximal methods: Proximal-gradient updates converge globally for fixed Y under a diminishing step size, while fixed sufficiently small steps converge to an O(α) neighborhood.The stated step-size condition is α_t < 1/L, where L is the gradient’s Lipschitz constant.
  • Proximal methods: The prox-prox method retains the original objective’s minimizers and has the same fixed-Y global convergence guarantee under the stated step-size conditions.Its update applies proximal gradient to the Moreau envelope of the regularizer.
  • Convergence behavior: Quadratically regularized PCA converges from five random initializations to the same globally optimal value, whereas nonnegative matrix factorization reaches initialization-dependent local optima.For nonnegative factorization, three trajectories share one value, one achieves a somewhat better value, and one is substantially worse.
  • Initialization and guarantees: SVD initialization applies across PCA-like models with mixed real, Boolean, categorical, and ordinal data, and can yield a substantially lower final objective than random starts.The initialization is constructed by expanding categorical columns and reinterpreting ordinal and Boolean columns numerically before scaling.
  • Global optimality: A global-optimality certificate can sometimes be obtained from the SVD of XY and a subgradient G satisfying ∥(1/γ)G + UV^T∥2 ≤ 1.The theorem also relates factored and rank-constrained formulations under the stated norm condition.

8 Choosing low rank models

The section explains how to choose rank and regularization using regularization paths, cross-validation, and information criteria, while balancing fit, generalization, denoising, and compression. Experiments show that cross-validation identifies the true rank and that regularization can compensate for excessive rank, but holdout selection for denoising remains unsettled.

  • Choosing model parameters: Cross-validation for denoising depends on holdout size, noise type, and data aspect ratio, and the optimal holdout size is not generally understood.Leaving out too few entries can overfit noise, while leaving out too many can underfit signal.
  • Choosing model parameters: Cross-validation is needed because higher rank and weaker regularization improve training fit while potentially overfitting noisy observations.The objective value alone cannot select k or γ because unregularized and higher-rank models always achieve lower empirical loss.
  • Choosing model parameters: The true rank k = 3 performs best on cross-validated error across observation counts, although more observations make overfitting higher ranks harder.The reported experiment averages results over five draws from the data-generating distribution.
  • Choosing model parameters: At 10% observation density, rank k = 3 performs best across regularization values; large ranks benefit from larger γ, whereas under-ranked models are harmed by it.Thus, restricting rank can substitute for explicit factor regularization in this setting.
  • Choosing model parameters: When the rank is correct, fit is insensitive to the number of observations; when rank is too high or low, additional observations improve fit.This result describes the dependence of model fit on observation count.

9 Implementations

The paper provides Python, Julia, and Spark implementations for fitting generalized low rank models, with support for heterogeneous data, missing entries, custom losses, regularizers, and parallel computation. Automatic modeling features can infer column types and produce interpretable low-dimensional embeddings.

  • Implementations: Three open-source implementations support GLRM fitting: serial Python, shared-memory parallel Julia, and distributed Scala using Spark.Julia and Spark use alternating proximal gradient, while Python uses alternating minimization with cvxpy subproblems.
  • Python implementation: GLRM.py accepts heterogeneous Boolean and numerical data, missing entries, selectable losses and regularizers, and alternating-minimization fitting.Its supported components include quadratic and ordinal losses, quadratic regularization, nonnegative constraints, and user-defined classes.
  • Julia implementation: LowRankModels uses proximal gradient fitting and supports observed-entry specifications, per-column losses, regularizers, rank selection, and custom losses or regularizers.The returned factors X and Y and convergence history are exposed by the fitting interface.
  • Julia implementation: LowRankModels provides shared-memory parallelism through Julia SharedArrays, allowing separate processes on one computer to access shared data and model blocks.This implementation is designed to fit models using multiple processes.
  • Automatic modeling: Automatic modeling detects column types, selects suitable losses, adds offsets, scales losses, ignores missing values, and fits a rank-k model to a data frame.The resulting GLRM can be fit with fit!.
  • Automatic modeling: On the MSQ data set, the automatically generated two-dimensional embedding separates positive from negative emotions along the y axis and remains interpretable.The data contain real-valued, Boolean, and ordinal measurements with approximately 6% missing values.

A Quadratically regularized PCA

This appendix introduces the quadratically regularized PCA problem and assumes an SVD of the data matrix with distinct positive nonzero singular values. The problem is presented as a special case with convenient spectral structure.

  • Problem setup: The quadratically regularized PCA problem uses a data matrix A whose SVD has distinct positive nonzero singular values.The appendix denotes the rank of A by r and writes its SVD as UΣV^T = A.

A.1 Solution

The appendix characterizes stationary points of quadratically regularized PCA through the singular structure of A and identifies which stationary points are global minima. Regularization activates singular directions above γ and leaves only the zero solution when γ exceeds the largest singular value.

  • Solution: The quadratically regularized PCA problem is the only problem in the paper’s treatment with an analytical solution.The appendix states that a solution is available in closed form.
  • Stationary points: At any stationary point, X^T X = YY^T, linking the factor Gram matrices through the optimality conditions.This equality follows by multiplying and rearranging the two stationarity equations.
  • Stationary points: Stationary factors lie in invariant subspaces associated with eigenvalues -γ ± σ_i, with the larger eigenvalues corresponding to paired singular vectors of A.The relevant eigendirections are (u_i, v_i) and (u_i, -v_i).
  • Active subspaces: An active subspace includes singular directions satisfying σ_i ≥ γ, and the corresponding factors have singular values √(σ_i − γ).The same singular values occur in X and Y because X^T X = YY^T.
  • Stationary points: The number of representative stationary points decreases as γ increases, and only X = 0, Y = 0 remains when γ > σ_1.The active-subspace count is controlled by the number of singular values at least as large as γ.
  • Global minima: Selecting the top singular values yields the global minimum, whereas other active-subspace choices produce stationary points with higher objective values.Each active subspace generates an orbit of stationary points under transformations of the factors, including orthogonal transformations.

A.2 Fixed points of alternating minimization

For quadratically regularized PCA, the only local minimum is global. The proof identifies nonoptimal stationary points by constructing perturbations that decrease the objective.

  • Theorem 2 establishes that quadratically regularized PCA has only one local minimum, and it is the global minimum.
  • Every stationary point has a factorization indexed by a subset Ω of singular-vector directions, with |Ω| ≤ k and d_i = σ_i − γ.
  • A stationary point is nonoptimal when some omitted singular value σ_j exceeds a selected value σ_i.
  • Perturbing a selected left singular direction toward an omitted direction produces a descent direction whenever σ_j > σ_i.
  • The objective change is 2ϵ^2d_i(σ_i − σ_j) + ϵ^4d_i^2, which is negative for sufficiently small ϵ under σ_j > σ_i.
Loading 1410.0342v4…