Publication Type

Journal Article

Version

acceptedVersion

Publication Date

11-2012

Abstract

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 Semi-Definiteness (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 real-world data sets.

Keywords

Similarity, Positive Semi-Definite (PSD) matrix, Positive Semi-Definite (PSD) Estimation, Row reduction, Incomplete Cholesky decomposition

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

IEICE Transactions on Information and Systems

Volume

E95-D

Issue

11

First Page

2599

Last Page

2612

ISSN

0916-8532

Identifier

10.1587/transinf.E95.D.2599

Publisher

Institute of Electronics, Information and Communication Engineers

Additional URL

http://doi.org/10.1587/transinf.E95.D.2599

Download

Share

COinS