
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Fast and Accurate PSD Matrix Estimation by Row Reduction
Hiroshi KUWAJIMA Takashi WASHIO EePeng LIM
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E95D
No.11
pp.25992612 Publication Date: 2012/11/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E95.D.2599
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: similarity, Positive SemiDefinite (PSD) matrix, Positive SemiDefinite (PSD) Estimation, row reduction, incomplete Cholesky decomposition,
Full Text: PDF(867.9KB)>>
Summary:
Fast and accurate estimation of missing relations, e.g., similarity, distance and kernel, among objects is now one of the most important techniques required by major data mining tasks, because the missing information of the relations is needed in many applications such as economics, psychology, and social network communities. Though some approaches have been proposed in the last several years, the practical balance between their required computation amount and obtained accuracy are insufficient for some class of the relation estimation. The objective of this paper is to formalize a problem to quickly and efficiently estimate missing relations among objects from the other known relations among the objects and to propose techniques called “PSD Estimation” and “Row Reduction” for the estimation problem. This technique uses a characteristic of the relations named “Positive SemiDefiniteness (PSD)” and a special assumption for known relations in a matrix. The superior performance of our approach in both efficiency and accuracy is demonstrated through an evaluation based on artificial and realworld data sets.

