Overview

This problem is equivalent to the low-rank approximation of matrix M, since

M = [m₁ m₂ ... m_n] ≈ [u₁ u₂ ... u_k] [v₁ v₂ ... v_n] = UV,

where each column of M is a data point, each column of U a basis vector and each column of V provides the coordinates of the corresponding column of M in the basis U. This class of problems is at the heart of many fields of applied mathematics and computer science (numerical linear algebra, statistics and data analysis, optimization, machine learning and data mining, signal and image processing, graph theory, and systems theory and control). There are used in a wide variety of applications. For example,

• hyperspectral unmixing: given a hyperspectral image, the goal is to recover the constitutive materials present in the image and then identify which pixels contain which material and in which quantity [1] --For example, in the image below, we can identify road surfaces, grass, trees and rooftops.

• recommender systems that predicts the preferences of users for a given product based on their attributes and their preferences --This is the problem behind the famous Netflix competition to predict preferences for movies [2].

• background subtraction that separates the moving objects from the background in a video sequence so that you can for example identify automatically some abnormal activities [3], and

• document analysis that aims at classifying the documents from a data set according to the topics they discuss [4].

There are two key aspects in low-rank matrix approximation problems of the form

1. The choice for the measure of the approximation error. Using the standard least squares error, that is, ∑_ij(M-UV)_ij², leads to principal component analysis (PCA) that can be solved for example using the truncated singular value decomposition (SVD). If data is missing, the problem can be cast as a weighted low-rank matrix approximation problem with error ∑_ij W_ij (M-UV)_ij² for some nonnegative weight matrix W. If we use the sum of the absolute values of the entries of the error ∑_ij |M-UV|_ij, we obtain yet another variant more robust to outliers (sometimes referred to as robust PCA).

2. The constraints that the factors U and V should satisfy. These constraints depend on the application at hand and allows to interpret the factors meaningfully. For example, k-means is equivalent to imposing the factor V to have a single non-zero entry in each column that is equal to one so that the columns of U are cluster centroids. Imposing component-wise nonnegativity on both factors U and V leads to nonnegative matrix factorization (NMF). For example, in document analysis, these nonnegativity constraints allow one to interpret the columns of the factor U as topics and the columns of the factor V indicates in which proportion each document discusses each topic. Another widely used variant is sparse PCA that imposes the factors (U and/or V) to be sparse.

This project will attack this class of problems with four different but complementary perspectives, each being a building block (BB) of COLORAMAP: computational complexity issues (BB1), provably correct algorithms (BB2), heuristics for difficult instances (BB3) and application-oriented aspects (BB4).

The main objectives of COLORAMAP will be to

• Resolve theoretical questions in order to improve our understanding of this generalized problem class, in particular characterize its computational complexity and evaluate the influence of different choices of feasible sets and objective functions.

• Analyze existing techniques and develop new algorithms with well-founded theoretical motivations.

• Develop new (meta-)heuristic algorithms that can handle difficult cases effectively.

• Use these techniques for applications, and develop new models based on specific applications.

If you are interested about this topic, you can also read my recent survey "Introduction to Nonnegative Matrix Factorization", SIAG/OPT Views and News 25 (1), pp. 7-16, 2017 [pdf] [arXiv], or the paper "Learning with Nonnegative Matrix Factorizations", SIAM News 25 (5), pp. 1-3, 2019. [link]

You can also watch the following video: https://www.youtube.com/watch?time_continue=1&v=HNvVKVPwB7s

References

[1] Ma, Bioucas-Dias, Chan, Gillis, Gader, Plaza, Ambikapathi and Chi, A Signal Processing Perspective on Hyperspectral Unmixing, IEEE Signal Process. Mag. 31(1):67-81, 2014.

[2] Koren, Bell and Volinsky, Matrix Factorization Techniques for Recommender Systems, IEEE Computer 42(8):30-37, 2009.

[3] Candès, Li, Ma, and Wright, Robust principal component analysis?, Journal of the ACM 58(3):11, 2011.

[4] Blei, Probabilistic topic models, Communications of the ACM 55(4):77-84, 2012.