A Divide-and-Conquer Method for Scalable Low-Rank Latent Matrix Pursuit
Authors:
- Yan PanYPYan Pan
- Hanjiang LaiHLHanjiang Lai
- Cong LiuCLCong Liu
- Shuicheng YanSYShuicheng Yan
- 1 June 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 524-531
Abstract
Data fusion, which effectively fuses multiple prediction lists from different kinds of features to obtain an accurate model, is a crucial component in various computer vision applications. Robust late fusion (RLF) is a recent proposed method that fuses multiple output score lists from different models via pursuing a shared low-rank latent matrix. Despite showing promising performance, the repeated full Singular Value Decomposition operations in RLF's optimization algorithm limits its scalability in real world vision datasets which usually have large number of test examples. To address this issue, we provide a scalable solution for large-scale low-rank latent matrix pursuit by a divide-and-conquer method. The proposed method divides the original low-rank latent matrix learning problem into two size-reduced sub problems, which may be solved via any base algorithm, and combines the results from the sub problems to obtain the final solution. Our theoretical analysis shows that with fixed probability, the proposed divide-and-conquer method has recovery guarantees comparable to those of its base algorithm. Moreover, we develop an efficient base algorithm for the corresponding sub problems by factorizing a large matrix into the product of two size-reduced matrices. We also provide high probability recovery guarantees of the base algorithm. The proposed method is evaluated on various fusion problems in object categorization and video event detection. Under comparable accuracy, the proposed method performs more than $180$ times faster than the state-of-the-art baselines on the CCV dataset with about 4,500 test examples for video event detection.
Keywords
This publication has 13 references indexed in Scilit:
- Active Subspace: Toward Scalable Low-Rank LearningNeural Computation, 2012
- Rank aggregation via nuclear norm minimization2011
- Contextualizing object detection and classification2011
- Robust principal component analysis?Journal of the ACM, 2011
- A Singular Value Thresholding Algorithm for Matrix CompletionSIAM Journal on Optimization, 2010
- Optimal Classifier Fusion in a Non-Bayesian Probabilistic FrameworkIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008
- Likelihood Ratio-Based Biometric Score FusionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2007
- A Visual Vocabulary for Flower Classification2006
- Multiple kernel learning, conic duality, and the SMO algorithm2004
- A theory of pseudoskeleton approximationsLinear Algebra and its Applications, 1997