Overview

https://erc.europa.eu/

Beyond Low-Rank Factorizations

eLinoR

Given a set of n data points xj (j=1,2,…,n), the starting point and main motivation behind eLinoR is to understand the underlying structure of this data. A fundamental and powerful tool to achieve this goal is linear dimensionality reduction: find a set of r basis vectors wk (k=1,2,…,r) and the corresponding weights hkj so that for all j: 

xj   ≈  ∑k wk hkj

This problem is equivalent to the low-rank matrix factorization (LRMF) of X, since 

X = [x1 x2 ... xn]   ≈   [w1 w2 ... wk] [h1 h2 ... hn] = WH,

where each column of X is a data point, each column of W a basis vector and each column of H provides the coordinates of the corresponding column of X in the basis W. 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).  LRMFs have known and still know tremedous success in these fields; see, e.g., here

However, LRMFs have two key limitations: 

1) They can only learn one layer of features, and hence are unable to mine interleaved features. 

2) They are linear models, and hence cannot model non-linear effects which are present in many applications. 

Let us illustrate this on the blind hyperspectral image unmixing problem. We represent a hyperspectral image as a matrix, X, where the jth column, X(:,j), corresponds to the spectral signature of the jth pixel.  If the spectral signatures of the constitutive materials present in the image (called endmembers) are collected as the columns of a matrix W, then according to the linear mixing model, the jth pixel can be written as X(:,j) ≈ ∑k W(:,k) H(k,j), where H(k,j) is the abundance of the kth endmember in the jth pixel. The figure below illustrates this decomposition using an example HSI taken from above a Walmart in Texas. 

Figure 1. On the left-hand side, we see the HSI visualized as a 3D volume. The first two dimensions correspond to the horizontal and vertical dimensions of an image, and the third dimension represents the different wavelengths at which the scene has been observed. On the right-hand side we see a decomposition of the HSI into the sum of different materials using nonnegative matrix factorization (NMF), an LRMF with nonnegativity constraint on the factors. For each material we see the spectral signature of the endmember (a column of Wi), and the abundance map of that endmember (a row of H, reshaped to match the dimensions of the original image). In the abundance maps, lighter tones represent larger abundances; the dominant materials in this scene are road, grass, trees, dirt, and two types of roof tops (including the large Walmart roof top). 

Non-linear LRMFs. The linear mixing model, which is still widely used in blind hyperspectral image unmixing, is not suitable in all situations. In particular, it has been well established that linear-quadratic (LQ) mixing models outperform linear models for data sets captured from 3-dimensional scenes, because nonlinearities are introduced by multiple light scattering. This situation is illustrated by the figure below; see for example [D+14] for more detail. Other examples of non-linear LRMF models include the following: X ≈ max(WH,0) [S22], the component-wise square (WH).2 X [L+22], or the Hadamard product of two low-rank factorizations (W1H1).*(W2H2) ≈ X [H+22], which all have been shown to be significantly more expressive than LRMFs. 

Figure 2. Illustration of the LQ mixing model: when the light interacts with two materials (this is shown in red), say the kth and the ℓth, the corresponding spectral signature is given by the component-wise product W(:,k) ◦ W(:,ℓ). The intensity of this interaction in pixel j is given by βk,ℓ,j which needs to be estimated for all k,ℓ,j, along with W and H.

Multi-layer/Deep LRMFs. What’s more, the materials in hyperspectral images can be organized in a hierarchical structure, e.g., different types of trees are three which themselves belong to the vegetation. Such structure can be identified automatically via deep LRMFs, where each layer of the decomposition corresponds to a level of the hierarchy [D+21]; see the figure below on the same HSI as above. Similarly many other types of data can be organized in a hierarchical structure, such as communities in graphs, and topics in a set of documents. 

Figure 3. Illustration of deep LRMFs on the Urban hyperspectral image. 

Goal of eLinoR. Non-linear and deep LRMFs have been introduced very recently, and have as yet been much less explored than LRMFs, especially when it comes to their theoretical understanding. In fact, most current works rely on heuristics and empirical validations. Therefore there is a need for the developments of the theoretical, algorithmic, and modelling aspects  of these generalized models; these three aspects will correspond to the three building blocks (BB) of eLinoR; see the figure on the right for an illustration. 

The main goal of eLinoR will be to bring the theoretical, algorithmic and modeling foundations to non-linear and deep LRMFs. This will enable the widespread and reliable use of these interpretable and expressible modes of unsupervised data analysis. 

References. 

[D+14] N. Dobigeon, J.-Y. Tourneret, C. Richard, J.C.M Bermudez, S. McLaughlin & A.O. Hero,  “Nonlinear unmixing of hyperspectral images: Models and algorithms”, IEEE Signal Processing Magazine 31 (1), 82-94, 2014.
[D+21] P. De Handschutter, N. Gillis & X. Siebert, “A survey on deep matrix factorizations”, Computer Science Review 42, 100423, 2021.
[H+22] N. Hyeon-Woo , M. Ye-Bin , T.-H. Oh, "FedPara: Low-rank Hadamard Product for Communication-Efficient Federated Learning", ICLR, 2022.
[L+22] L. Loconte, N. Di Mauro, R. Peharz, A. Vergari, “Your Knowledge Graph Embeddings are Secretly Circuits and You Should Treat Them as Such”, UAI Workshop on Tractable Probabilistic Modeling, 2022.
[S22] L. K. Saul, “A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data”, SIAM J. on Mathematics of Data Science 4 (2), 431-463, 2022. 

Why eLinoR? Elinor is the name of my first daughter (I have two; see them here).