Metric Correction of Similarities Based on Orthogonal Decomposition

Abstract

Raw data in modern machine learning usually appear as similarities or dissimilarities between members of a limited set. A positive definite similarity matrix represents a limited set of elements immersed in some metric space with dimensionality right up to the matrix size with similarities considered as scalar products. In a case of a nonpositive definite similarity matrix, it needs metric correction of similarities to be considered as scalar products. The known discrete Karhunen-Loeve expansion is usually used to reduce the dimensionality of the similarity matrix by removing eigenvectors corresponded to negative eigenvalues. As a result, a new similarity matrix of the reduced size is calculated to immerse members of a limited set in a reduced space of eigenvectors corresponded only to positive eigenvalues with data dispersion reduced. According to an orthogonal decomposition based metric correction here, it is proposed not to remove, but change negative eigenvalues to become positive ones. As a result, such an optimal correction preserves the dimensionality and dispersion of raw data.