Title: A Greedy Algorithm to Construct L1 Graph with Ranked Dictionary
Abstract: $$\mathcal {L}_1$$ graph is an effective way to represent data samples in many graph-oriented machine learning applications. Its original construction algorithm is nonparametric, and the graphs it generates may have high sparsity. Meanwhile, the construction algorithm also requires many iterative convex optimization calculations and is very time-consuming. Such characteristics would severely limit the application scope of $$\mathcal {L}_1$$ graph in many real-world tasks. In this paper, we design a greedy algorithm to speed up the construction of $$\mathcal {L}_1$$ graph. Moreover, we introduce the concept of “Ranked Dictionary” for $$\mathcal {L}_1$$ minimization. This ranked dictionary not only preserves the locality but also removes the randomness of neighborhood selection during the process of graph construction. To demonstrate the effectiveness of our proposed algorithm, we present our experimental results on several commonly-used datasets using two different ranking strategies: one is based on Euclidean metric, and another is based on diffusion metric.
Publication Year: 2016
Publication Date: 2016-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot