Konstantin Usevich

Konstantin Usevich, Ivan Markovsky

The structured low-rank approximation problem for general affine structures, weighted 2-norms and fixed elements is considered. The variable projection principle is used to reduce the dimensionality of the optimization problem. Algorithms for evaluation of the cost function, the gradient and an approximation of the Hessian are developed. For $m \times n$ mosaic Hankel matrices the algorithms have complexity $O(m^2 n)$.

Konstantin Usevich, Philippe Dreesen, Mariya Ishteva

Decoupling multivariate polynomials is useful for obtaining an insight into the workings of a nonlinear mapping, performing parameter reduction, or approximating nonlinear functions. Several different tensor-based approaches have been proposed independently for this task, involving different tensor representations of the functions, and ultimately leading to a canonical polyadic decomposition. We first show that the involved tensors are related by a linear transformation, and that their CP decompositions and uniqueness properties are closely related. This connection provides a way to better assess which of the methods should be favored in certain problem settings, and may be a starting point to unify the two approaches. Second, we show that taking into account the previously ignored intrinsic structure in the tensor decompositions improves the uniqueness properties of the decompositions and thus enlarges the applicability range of the methods.

Joppe De Jonghe, Konstantin Usevich, Philippe Dreesen et al.

The decoupling of multivariate functions is a powerful modeling paradigm for learning multivariate input-output relations from data. For the single-layer case, established CPD-based methods are available, but the multi-layer case remained largely unexplored. This work introduces a tensor-based framework for multi-layer decoupling, which is based on ParaTuck-type tensor decompositions and constrained optimization. We provide theoretical justification behind the considered tensor decompositions and parameterizations. Furthermore, we formulate a structured coupled matrix-tensor factorization that incorporates both Jacobian and function evaluations, together with a bilevel optimization approach for adaptively balancing first- and zeroth-order information. The feasibility of the proposed methodology is illustrated on synthetic systems, a nonlinear system identification benchmark and neural network compression.

Konstantin Usevich, Ricardo Borsoi, Clara Dérand et al.

Polynomial Neural Networks (PNNs) possess a rich algebraic and geometric structure. However, their identifiability -- a key property for ensuring interpretability -- remains poorly understood. In this work, we present a comprehensive analysis of the identifiability of deep PNNs, including architectures with and without bias terms. Our results reveal an intricate interplay between activation degrees and layer widths in achieving identifiability. As special cases, we show that architectures with non-increasing layer widths are generically identifiable under mild conditions, while encoder-decoder networks are identifiable when the decoder widths do not grow too rapidly compared to the activation degrees. Our proofs are constructive and center on a connection between deep PNNs and low-rank tensor decompositions, and Kruskal-type uniqueness theorems. We also settle an open conjecture on the dimension of PNN's neurovarieties, and provide new bounds on the activation degrees required for it to reach the expected dimension.

Ricardo Augusto Borsoi, Konstantin Usevich, David Brie et al.

Coupled tensor decompositions (CTDs) perform data fusion by linking factors from different datasets. Although many CTDs have been already proposed, current works do not address important challenges of data fusion, where: 1) the datasets are often heterogeneous, constituting different "views" of a given phenomena (multimodality); and 2) each dataset can contain personalized or dataset-specific information, constituting distinct factors that are not coupled with other datasets. In this work, we introduce a personalized CTD framework tackling these challenges. A flexible model is proposed where each dataset is represented as the sum of two components, one related to a common tensor through a multilinear measurement model, and another specific to each dataset. Both the common and distinct components are assumed to admit a polyadic decomposition. This generalizes several existing CTD models. We provide conditions for specific and generic uniqueness of the decomposition that are easy to interpret. These conditions employ uni-mode uniqueness of different individual datasets and properties of the measurement model. Two algorithms are proposed to compute the common and distinct components: a semi-algebraic one and a coordinate-descent optimization method. Experimental results illustrate the advantage of the proposed framework compared with the state of the art approaches.

Ricardo Borsoi, Konstantin Usevich, Marianne Clausel

The groundbreaking performance of deep neural networks (NNs) promoted a surge of interest in providing a mathematical basis to deep learning theory. Low-rank tensor decompositions are specially befitting for this task due to their close connection to NNs and their rich theoretical results. Different tensor decompositions have strong uniqueness guarantees, which allow for a direct interpretation of their factors, and polynomial time algorithms have been proposed to compute them. Through the connections between tensors and NNs, such results supported many important advances in the theory of NNs. In this review, we show how low-rank tensor methods--which have been a core tool in the signal processing and machine learning communities--play a fundamental role in theoretically explaining different aspects of the performance of deep NNs, including their expressivity, algorithmic learnability and computational hardness, generalization, and identifiability. Our goal is to give an accessible overview of existing approaches (developed by different communities, ranging from computer science to mathematics) in a coherent and unified way, and to open a broader perspective on the use of low-rank tensor decompositions for the theory of deep NNs.

Yassine Zniyed, Konstantin Usevich, Sebastian Miron et al.

Activation functions (AFs) are an important part of the design of neural networks (NNs), and their choice plays a predominant role in the performance of a NN. In this work, we are particularly interested in the estimation of flexible activation functions using tensor-based solutions, where the AFs are expressed as a weighted sum of predefined basis functions. To do so, we propose a new learning algorithm which solves a constrained coupled matrix-tensor factorization (CMTF) problem. This technique fuses the first and zeroth order information of the NN, where the first-order information is contained in a Jacobian tensor, following a constrained canonical polyadic decomposition (CPD). The proposed algorithm can handle different decomposition bases. The goal of this method is to compress large pretrained NN models, by replacing subnetworks, {\em i.e.,} one or multiple layers of the original network, by a new flexible layer. The approach is applied to a pretrained convolutional neural network (CNN) used for character classification.

Jianze Li, Konstantin Usevich, Pierre Comon

In this paper, we study the approximate orthogonal diagonalization problem of third order symmetric tensors. We define several classes of approximately diagonal tensors, including the ones corresponding to the stationary points of this problem. We study the relationships between these classes, and other well-known objects, such as tensor Z-eigenvalue and Z-eigenvector. We also prove results on convergence of the cyclic Jacobi (or Jacobi CoM2) algorithm.

Jonathan Gillard, Konstantin Usevich

In this paper we consider the low-rank matrix completion problem with specific application to forecasting in time series analysis. Briefly, the low-rank matrix completion problem is the problem of imputing missing values of a matrix under a rank constraint. We consider a matrix completion problem for Hankel matrices and a convex relaxation based on the nuclear norm. Based on new theoretical results and a number of numerical and real examples, we investigate the cases when the proposed approach can work. Our results highlight the importance of choosing a proper weighting scheme for the known observations.

Jianze Li, Konstantin Usevich, Pierre Comon

In this paper, we consider a family of Jacobi-type algorithms for simultaneous orthogonal diagonalization problem of symmetric tensors. For the Jacobi-based algorithm of [SIAM J. Matrix Anal. Appl., 2(34):651--672, 2013], we prove its global convergence for simultaneous orthogonal diagonalization of symmetric matrices and 3rd-order tensors. We also propose a new Jacobi-based algorithm in the general setting and prove its global convergence for sufficiently smooth functions.

Pierre Comon, Yang Qi, Konstantin Usevich

In this paper, we study a polynomial decomposition model that arises in problems of system identification, signal processing and machine learning. We show that this decomposition is a special case of the X-rank decomposition --- a powerful novel concept in algebraic geometry that generalizes the tensor CP decomposition. We prove new results on generic/maximal rank and on identifiability of a particular polynomial decomposition model. In the paper, we try to make results and basic tools accessible for general audience (assuming no knowledge of algebraic geometry or its prerequisites).

Konstantin Usevich, Ivan Markovsky

We consider the problem of fitting a set of points in Euclidean space by an algebraic hypersurface. We assume that points on a true hypersurface, described by a polynomial equation, are corrupted by zero mean independent Gaussian noise, and we estimate the coefficients of the true polynomial equation. The adjusted least squares estimator accounts for the bias present in the ordinary least squares estimator. The adjusted least squares estimator is based on constructing a quasi-Hankel matrix, which is a bias-corrected matrix of moments. For the case of unknown noise variance, the estimator is defined as a solution of a polynomial eigenvalue problem. In this paper, we present new results on invariance properties of the adjusted least squares estimator and an improved algorithm for computing the estimator for an arbitrary set of monomials in the polynomial equation.