Linearly-scalable learning of smooth low-dimensional patterns with permutation-aided entropic dimension reduction

The problem of efficiently re-arranging or permuting data in some desired way, for example, deploying sorting algorithms, belongs to the most long-standing questions in computer science and applied mathematics [1]. Many impressive theoretical and practical algorithmic results in this area could be established in past decades for problems of one-and low-dimensional data sorting, where one seeks for a monotonic (ascending or descending) ordering in one or several data dimensions [1-3]. In their seminal work, Garrett Birkhoff and John von Neumann have established a mathematical relationship between permutations of the T -component vector and the multiplication of this vector with T T double-stochastic Markovian operator P, containing only one 1.0 in every row and every column, with all other matrix elements being equal to zero [4, 5]. Such a'crisp' double-stochastic Markov operator (containing only zeroes and ones) is referred to as a permutation matrix - as opposed to the'fuzzy' doublestochastic Markov operators that contain elements that are between zero and one. For a vector with T elements there exist T! of all possible ('crisp') permutation matrices P, that build the edges of the T (T 2)-dimensional polytope of all'fuzzy' (or'soft') double-stochastic Markov matrices [6, 7]. NP-complexity of the original'crisp' permutation problem - arising when extending the generic sorting and permutation problems (satisfying desired criteria) from one to several dimensions - has led to a growing popularity of methods based on'soft' relaxations of the permutation matrix, ignited by several very successful mathematical and algorithmic approaches that dwell on the spectral decomposition of the'soft'/'fuzzy' Markov operator [8, 9] and allowing for a metastable decomposition and a reduced analysis of high-dimensional systems from various areas [10-12]. Further, the ideas of'soft' Markovian relaxation for permutations were explored in the areas of graph-matching and graph-alignment, leading to new approaches to these problems - like the new spectral criteria for checking the matching of this'fuzzy' /continuous relaxation to the original'crisp' graph-matching permutation [13]. These'soft' permutation ideas were further applied to the supervised graph-permutation and graph-alignment problems [14-16]. In the literature, it is argued that the'soft' permutations allow reducing NP-hard to P-hard algorithmic solutions, but at the same time is not clear how the loss of'crispness' for the resulting'soft' permutation matrices, can avoid leading to such'soft' permutation relaxation extremes as the stochastic matrices with all of the elements being equal to