The Singular Value Decomposition over Completed Idempotent Semifields Articles uri icon

publication date

  • September 2020

start page

  • 1577

issue

  • 9

volume

  • 8

International Standard Serial Number (ISSN)

  • 2227-7390

abstract

  • In this paper, we provide a basic technique for Lattice Computing: an analogue of the Singular Value Decomposition for rectangular matrices over complete idempotent semifields (i-SVD). These algebras are already complete lattices and many of their instances-the complete schedule algebra or completed max-plus semifield, the tropical algebra, and the max-times algebra-areuseful in a range of applications, e.g., morphological processing. We further the task of eliciting the relation between i-SVD and the extension of Formal Concept Analysis to complete idempotent semifields (K-FCA) started in a prior work. We find out that for a matrix with entries considered in a complete idempotent semifield, the Galois connection at the heart of K-FCA provides two basis ofleft- and right-singular vectors to choose from, for reconstructing the matrix. These are join-dense or meet-dense sets of object or attribute concepts of the concept lattice created by the connection, and they are almost surely not pairwise orthogonal. We conclude with an attempt analogue of the fundamental theorem of linear algebra that gathers all results and discuss it in the wider setting of matrix factorization.

keywords

  • complete idempotent semifields; formal concept analysis; idempotent singular value decomposition; max-plus algebra; min-plus algebra; schedule algebra; tropical algebra