Min-plus algebraic low rank matrix approximation: a new method for revealing structure in networks
For network analysts, this provides a new method to reveal predominant structures that classical low-rank approximations miss.
The paper introduces min-plus low rank matrix approximation, which uses min and plus operations instead of plus and times, enabling detection of different structures than PCA, particularly for network analysis.
In this paper we introduce min-plus low rank matrix approximation. By using min and plus rather than plus and times as the basic operations in the matrix multiplication; min-plus low rank matrix approximation is able to detect characteristically different structures than classical low rank approximation techniques such as Principal Component Analysis (PCA). We also show how min-plus matrix algebra can be interpreted in terms of shortest paths through graphs, and consequently how min-plus low rank matrix approximation is able to find and express the predominant structure of a network.