iccv iccv2013 iccv2013-122 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ameet Talwalkar, Lester Mackey, Yadong Mu, Shih-Fu Chang, Michael I. Jordan
Abstract: Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. In each case, we obtain stateof-the-art results and order-of-magnitude speed ups.
Reference: text
sentIndex sentText sentNum sentScore
1 edu Abstract Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. [sent-7, score-0.663]
2 Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. [sent-8, score-0.462]
3 Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. [sent-9, score-0.121]
4 In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. [sent-10, score-0.435]
5 This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. [sent-11, score-0.308]
6 We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. [sent-12, score-0.446]
7 Subspace segmentation techniques model these classes of data by recovering bases for the multiple underlying subspaces [10, 7]. [sent-21, score-0.175]
8 Applications include image clustering [7], segmentation of images, video, and motion [30, 6, 26], and affinity graph construction for semi-supervised learning [32]. [sent-22, score-0.365]
9 One promising, convex formulation of the subspace segmentation problem is the low-rank representation (LRR) program of Liu et al. [sent-23, score-0.378]
10 Here, M is an input matrix of datapoints drawn from multiple subspaces, ? [sent-29, score-0.117]
11 LRR segments the columns ∗ 2,1 of M into subspaces using the solution Zˆ, and, along with its extensions (e. [sent-36, score-0.118]
12 , LatLRR [19] and NNLRS [32]), admits strong guarantees of correctness and strong empirical performance in clustering and graph construction applications. [sent-38, score-0.254]
13 Much of the computational burden in solving LRR stems from the nuclear norm penalty, which is known to encourage low-rank solutions, so one might hope to leverage the large body of past work on parallel and distributed matrix factorization [11, 23, 8, 3 1, 21] to improve the scalability of LRR. [sent-41, score-0.247]
14 (1), and this nondecomposable constraint introduces new algorithmic and analytic challenges that do not arise in decomposable matrix factorization problems. [sent-44, score-0.162]
15 To address these challenges, we develop, analyze, and evaluate a provably accurate divide-and-conquer approach to large-scale subspace segmentation that specifically accounts for the non-decomposable structure of the LRR problem. [sent-45, score-0.423]
16 Our contributions are three-fold: Algorithm: We introduce a parallel, divide-and-conquer approximation algorithm for LRR that is suitable for large- scale subspace segmentation problems. [sent-46, score-0.358]
17 Scalability is achieved by dividing the original LRR problem into computationally tractable and communication-free subproblems, solving the subproblems in parallel, and combining the re33553436 sults using a technique from randomized matrix approximation. [sent-47, score-0.119]
18 Our algorithm, which we call DFC-LRR, is based on the principles of the Divide-Factor-Combine (DFC) framework [21] for decomposable matrix factorization but can cope with the non-decomposable constraints of LRR. [sent-48, score-0.143]
19 Analysis: We characterize the segmentation behavior of our new algorithm, showing that DFC-LRR maintains the segmentation guarantees ofthe original LRR algorithm with high probability, even while enjoying substantial speed-ups over its namesake. [sent-49, score-0.339]
20 Moreover, since our ultimate goal is subspace segmentation and not matrix recovery, our theory guarantees correctness under a more substantial reduction of problem complexity than the work of [21] (see Sec. [sent-51, score-0.527]
21 Applications: We first present results on face clustering and synthetic subspace segmentation to demonstrate that DFC-LRR achieves accuracy comparable to LRR in a fraction of the time. [sent-54, score-0.536]
22 Leveraging the favorable computational properties of DFC-LRR, we propose a scalable strategy for constructing such subspace affinity graphs. [sent-57, score-0.355]
23 We apply our methodology to a variety of computer vision tasks multimedia event detection, concept detection, and image tagging demonstrating an order of magnitude improvement in speed and accuracy that exceeds the state of the art. [sent-58, score-0.126]
24 In Section 2 we first review the low-rank representation approach to subspace segmentation and then introduce our novel DFC-LRR algorithm. [sent-60, score-0.358]
25 We present subspace segmentation results on simulated and real-world data in Section 4. [sent-63, score-0.358]
26 as the compact singular value decomposition (SVD) of M, where rank(M) = r, ΣM is a diagonal matrix of the r non-zero singular values and UM ∈ Rm×r and VM ∈ Rn×r are the associated left and right singular vectors o∈f MR. [sent-68, score-0.182]
27 Divide-and-Conquer Segmentation In this section, we review the LRR approach to subspace segmentation and present our novel algorithm, DFC-LRR. [sent-71, score-0.358]
28 Subspace Segmentation via LRR In the robust subspace segmentation problem, we observe a matrix M = L0 + S0 ∈ Rm×n, where the columns of L0 are datapoints drawn fro∈m multiple independent subspaces,1 and S0 is a column-sparse outlier matrix. [sent-74, score-0.619]
29 Our goal is to identify the subspace associated with each column of L0, despite the potentially gross corruption introduced by S0. [sent-75, score-0.278]
30 0 for the row space of L0, sometimes termed the shape iteration matrix, is block diagonal whenever the columns of L0 lie in multiple independent subspaces [10]. [sent-77, score-0.211]
31 Hence, we can achieve accurate segmentation by first recovering the row space of L0. [sent-78, score-0.154]
32 Importantly, the LRR solution comes with a guarantee of correctness: the column space of Zˆ is exactly equal to the row space of L0 whenever certain technical conditions are met [18] (see Sec. [sent-81, score-0.152]
33 Moreover, as we will show in this work, LRR is also well-suited to the construction of affinity graphs for semisupervised learning. [sent-83, score-0.198]
34 In this setting, the goal is to define an affinity graph in which nodes correspond to data points and edge weights exist between nodes drawn from the same subspace. [sent-84, score-0.144]
35 LRR can thus be used to recover the block-sparse structure of the graph’s affinity matrix, and these affinities can be used for semi-supervised label propagation. [sent-85, score-0.163]
36 Divide-Factor-Combine LRR (DFC-LRR) We now present our scalable divide-and-conquer algorithm, called DFC-LRR, for LRR-based subspace segmentation. [sent-88, score-0.277]
37 D step - Divide input matrix into submatrices: DFCLRR randomly partitions the columns of M into t l-column submatrices, {C1, . [sent-91, score-0.126]
38 (2) sum is the 33553447 where the input matrix M is used as a dictionary but only a subset of columns is used as the observations. [sent-102, score-0.126]
39 Theoretical Analysis Despite the significant reduction in computational complexity, DFC-LRR provably maintains the strong theoretical guarantees of the LRR algorithm. [sent-126, score-0.171]
40 3 Intuitively, when the coherence μ is small, information is well-distributed across the rows of a matrix, and the row space is easier to recover from outlier corruption. [sent-147, score-0.145]
41 co Lnesttant γ∗ (depending on μ and r) for which the column space of e√xactly equals the row space of L0 whenever λ = 3/(7? [sent-154, score-0.111]
42 Zˆ Zˆ In other words, LRR can exactly recover the row space of L0 even when a constant fraction γ∗ of the columns has been corrupted by outliers. [sent-157, score-0.219]
43 High Probability Subspace Segmentation Our main theoretical result shows that, with high proba- bility and under the same conditions that guarantee the accuracy of LRR, DFC-LRR also exactly recovers the row space of L0. [sent-161, score-0.127]
44 Recall that in our independent subspace setting accurate row space recovery is tantamount to correct segmentation of the columns of L0. [sent-162, score-0.53]
45 Then there exists a constant γ∗ (depending on μ and r) for which the column space of Zˆproj exac√tly equals the row space of L0 whenever λ = 3/(7? [sent-167, score-0.111]
46 3 establishes that, like LRR, DFC-LRR can tolerate a constant fraction of its data points being corrupted and still recover the correct subspace segmentation of the clean data points with high probability. [sent-187, score-0.48]
47 3 guarantees high probability recovery for DFC-LRR even when the subproblem size l is logarithmic in n. [sent-190, score-0.135]
48 Notably, this column sampling complexity is better than that established by [21] in the matrix factorization setting: we require O(r log n) columns sampled, while [21] requires in the worst case Ω(n) columns for matrix completion and Ω((r log n)2) for robust matrix factorization. [sent-192, score-0.436]
49 Experiments We now explore the empirical performance of DFCLRR on a variety of simulated and real-world datasets, first for the traditional task of robust subspace segmentation and next for the more complex task of graph-based semi-supervised learning. [sent-194, score-0.358]
50 Our synthetic datasets satisfy the theoretical assumptions of low rank, incoherence, and a small fraction of corrupted columns, while our real-world datasets violate these criteria. [sent-196, score-0.145]
51 For the subspace segmentation experiments, we set the regularization parameter to the values suggested in previous works [18, 17], while in ? [sent-198, score-0.358]
52 , the time of the longest running subproblem plus the time required to combine submatrix estimates via column projection. [sent-207, score-0.118]
53 We focus on the standard robust subspace segmentation task of identifying the subspace associated with each input datapoint. [sent-216, score-0.592]
54 1 Simulations To construct our synthetic robust subspace segmentation datasets, we first generate ns datapoints from each of k independent r-dimensional subspaces of Rm, in a manner similar to [18]. [sent-219, score-0.551]
55 For each subspace i, we independently select a basis Ui uniformly from all matrices in Rm×r with orthonormal columns and a matrix Ti ∈ Rr×ns of independent entries each distributed uniformly in [0, 1] . [sent-220, score-0.407]
56 We form the matrix Xi ∈ Rm×ns of samples from subspace i via Xi = UiTi and∈ le Rt X0 ∈ Rm×kns = [X1 . [sent-221, score-0.293]
57 For a given outlier fraction γ we next generate an additional no = 1−γγkns independent outlier samples, denoted by S ∈ Rm×no . [sent-225, score-0.171]
58 Each outlier sample has independent bNy( 0S, σ ∈2) Rentries, where σ is the average absolute value of Nthe( 0en,σtries of the kns original samples. [sent-226, score-0.156]
59 We create the input matrix M ∈ Rm×n, where n = kns + no, as a random permutation ∈o fR the columns of [X0 S] . [sent-227, score-0.205]
60 Figure 3: Trade-off between computation and segmentation accuracy on face recognition experiments. [sent-279, score-0.179]
61 and identify the outlier columns in S, using the same criterion as defined in [18]. [sent-285, score-0.118]
62 Figure 1(b) shows corresponding timing results for the accuracy results presented in Figure 1(a). [sent-292, score-0.129]
63 These timing results show substantial speedups in DFC-LRR relative to LRR with a modest tradeoff in accuracy as denoted in Figure 1(a). [sent-293, score-0.185]
64 Note that we only report timing results for values of γ for which DFC-LRR was successful in all 10 trials, i. [sent-294, score-0.107]
65 Moreover, Figure 1(c) shows timing results using the same × parameter values, except with a fixed fraction of outliers (γ = 0. [sent-298, score-0.15]
66 These timing results also show speedups with minimal loss of accuracy, as in all of these timing experiments, LRR and DFC-LRR were successful in all trials using the same criterion defined in [18] and used in our phase transition experiments of Figure 1(a). [sent-302, score-0.302]
67 2 Face Clustering We next demonstrate the comparable quality and increased performance of DFC-LRR relative to LRR on real data, namely, a subset of Extended Yale Database B,6 a standard face benchmarking dataset. [sent-307, score-0.108]
68 4 8A×s 4n2opteidxe ilns previous work [3], a low-dimensional subspace can be effectively used to model face images from one person, and hence face clustering is a natural application of subspace segmentation. [sent-309, score-0.566]
69 Moreover, as illustrated in Figure 2, a significant portion of the faces in this dataset are “corrupted” by shadows, and hence this collection of images is an ideal benchmark for robust subspace segmentation. [sent-310, score-0.234]
70 Next, we use the resulting low-rank coefficient matrix to compute an affinity matrix UZˆUZ? [sent-313, score-0.196]
71 contains the top left singular vectors of The affinity matrix is used to cluster the data into k = 10 clusters (corresponding to the 10 human subjects) via spectral embedding (to obtain a 10D feature representation) followed by k-means. [sent-315, score-0.178]
72 Following [17], the comparison of different clustering methods relies on segmentation accuracy. [sent-316, score-0.156]
73 We evaluate clustering performance of both LRR and DFCLRR by computing segmentation accuracy as in [17], i. [sent-318, score-0.178]
74 The segmentation accuracy is then computed by averaging the percentage of correctly classified data over all classes. [sent-321, score-0.146]
75 edu / ˜l eekc / Ext Ya l at aba s e on eD 33554470 segmentation accuracy, respectively, for LRR and for DFCLRR with varying numbers of subproblems (i. [sent-324, score-0.184]
76 Classical graph construction methods separately calculate the outgoing edges for each sample. [sent-332, score-0.131]
77 Recent work in computer vision has illustrated the utility of global graph construction strategies using graph Laplacian [9] or matrix low-rank [32] based regularizers. [sent-334, score-0.256]
78 L1 regularization has also been effectively used to encourage sparse graph construction [5, 13]. [sent-335, score-0.16]
79 Building upon the success of global construction methods and noting the connection between subspace segmentation and graph construction as described in Section 2. [sent-336, score-0.554]
80 2 Graph Construction Algorithms The three graph construction schemes we evaluate are described below. [sent-359, score-0.131]
81 , NNLRS [32], LLE graph [28], L1-graph [5]) due to either scalability concerns or because prior work has already demonstrated inferior performance relative to the SPG algorithm defined below [32]. [sent-362, score-0.107]
82 Subsequent work, entitled sparse probability graph (SPG) [13] enforced positive graph weights. [sent-375, score-0.161]
83 wx ≥ 0, (3) where x is a feature representation of a sample and Dx is the basis matrix for x constructed from its nk nearest neighbors. [sent-382, score-0.117]
84 SLR-graph: Our novel graph construction method contains two-steps: first LRR or DFC-LRR is performed on the entire data set to recover the intrinsic low-rank clustering structure. [sent-384, score-0.2]
85 We then treat the resulting low-rank coefficient matrix Z as an affinity matrix, and for sample xi, the nk samples with largest affinities to xi are selected to form a basis matrix and used to solve the SPG optimization described by Problem (3). [sent-385, score-0.248]
86 Table 1: Mean average precision (mAP) (0-1) scores for various graph construction methods. [sent-413, score-0.131]
87 We then use a given graph structure to perform semisupervised label propagation using an efficient label propagation algorithm [27] that enjoys a closed-form solution and often achieves the state-of-the-art performance. [sent-454, score-0.225]
88 Table 1 summarizes the results of our semi-supervised learning experiments using the three graph construction techniques defined in Section 4. [sent-468, score-0.131]
89 Conclusion Our primary goal in this work was to introduce a provably accurate algorithm suitable for large-scale low- rank subspace segmentation. [sent-478, score-0.327]
90 While some contemporaneous work [1] also aims at scalable subspace segmentation, this method offers no guarantee of correctness. [sent-479, score-0.298]
91 In contrast, DFC-LRR provably preserves the theoretical recovery guarantees of the LRR program. [sent-480, score-0.192]
92 Moreover, our divide-and-conquer approach achieves empirical accuracy comparable to state-of-the-art methods while obtaining linear to superlinear computational gains, both on standard subspace segmentation tasks and on novel applications to semi-supervised learning. [sent-481, score-0.437]
93 , LatLRR in the setting of standard subspace segmentation and NNLRS in the graph-based semi-supervised learning setting. [sent-484, score-0.358]
94 The same techniques may prove useful in developing scalable approximations to other convex formulations for subspace segmentation, e. [sent-485, score-0.297]
95 Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. [sent-607, score-0.111]
96 Exact subspace segmentation and outlier detection by low-rank representation. [sent-619, score-0.409]
97 Latent low-rank representation for subspace segmentation and feature extraction. [sent-626, score-0.358]
98 Unsupervised segmentation of natural images via lossy data compression. [sent-710, score-0.124]
99 Scalable coordinate descent approaches to parallel matrix factorization for recommender systems. [sent-719, score-0.164]
100 Non-negative low rank and sparse graph for semi-supervised learning. [sent-728, score-0.123]
wordName wordTfidf (topN-words)
[('lrr', 0.818), ('subspace', 0.234), ('segmentation', 0.124), ('spg', 0.118), ('timing', 0.107), ('dfclrr', 0.098), ('dfc', 0.079), ('kns', 0.079), ('affinity', 0.078), ('rm', 0.068), ('columns', 0.067), ('graph', 0.066), ('construction', 0.065), ('provably', 0.065), ('ccv', 0.064), ('proj', 0.064), ('factorization', 0.062), ('mfcc', 0.061), ('subproblems', 0.06), ('matrix', 0.059), ('nnlrs', 0.059), ('datapoints', 0.058), ('benchmarking', 0.053), ('outlier', 0.051), ('subspaces', 0.051), ('recovery', 0.049), ('correctness', 0.047), ('stip', 0.046), ('uz', 0.046), ('submatrices', 0.046), ('guarantees', 0.044), ('column', 0.044), ('fraction', 0.043), ('parallel', 0.043), ('scalable', 0.043), ('subproblem', 0.042), ('corrupted', 0.042), ('singular', 0.041), ('scalability', 0.041), ('ameet', 0.039), ('latlrr', 0.039), ('propagation', 0.039), ('speedups', 0.037), ('whenever', 0.037), ('recover', 0.037), ('semisupervised', 0.035), ('superlinear', 0.035), ('theoretical', 0.034), ('face', 0.033), ('submatrix', 0.032), ('classeme', 0.032), ('clustering', 0.032), ('ns', 0.032), ('tagging', 0.031), ('wx', 0.031), ('trials', 0.031), ('videos', 0.03), ('row', 0.03), ('sparse', 0.029), ('event', 0.029), ('rank', 0.028), ('moreover', 0.028), ('maintains', 0.028), ('nk', 0.027), ('coherence', 0.027), ('multibody', 0.027), ('independent', 0.026), ('synthetic', 0.026), ('wright', 0.026), ('affinities', 0.025), ('lowrank', 0.024), ('factored', 0.024), ('liu', 0.024), ('mz', 0.024), ('yale', 0.024), ('cheng', 0.024), ('multimedia', 0.024), ('label', 0.023), ('columbia', 0.022), ('comparable', 0.022), ('decomposable', 0.022), ('accuracy', 0.022), ('guarantee', 0.021), ('stochastic', 0.021), ('distributed', 0.021), ('nuclear', 0.021), ('um', 0.02), ('methodology', 0.02), ('conditions', 0.02), ('graphs', 0.02), ('phase', 0.02), ('convex', 0.02), ('vl', 0.02), ('null', 0.02), ('arise', 0.019), ('svd', 0.019), ('vertex', 0.019), ('substantial', 0.019), ('problems', 0.019), ('completion', 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000004 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
Author: Ameet Talwalkar, Lester Mackey, Yadong Mu, Shih-Fu Chang, Michael I. Jordan
Abstract: Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. In each case, we obtain stateof-the-art results and order-of-magnitude speed ups.
2 0.31518185 93 iccv-2013-Correlation Adaptive Subspace Segmentation by Trace Lasso
Author: Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan
Abstract: This paper studies the subspace segmentation problem. Given a set of data points drawn from a union of subspaces, the goal is to partition them into their underlying subspaces they were drawn from. The spectral clustering method is used as the framework. It requires to find an affinity matrix which is close to block diagonal, with nonzero entries corresponding to the data point pairs from the same subspace. In this work, we argue that both sparsity and the grouping effect are important for subspace segmentation. A sparse affinity matrix tends to be block diagonal, with less connections between data points from different subspaces. The grouping effect ensures that the highly corrected data which are usually from the same subspace can be grouped together. Sparse Subspace Clustering (SSC), by using ?1-minimization, encourages sparsity for data selection, but it lacks of the grouping effect. On the contrary, Low-RankRepresentation (LRR), by rank minimization, and Least Squares Regression (LSR), by ?2-regularization, exhibit strong grouping effect, but they are short in subset selection. Thus the obtained affinity matrix is usually very sparse by SSC, yet very dense by LRR and LSR. In this work, we propose the Correlation Adaptive Subspace Segmentation (CASS) method by using trace Lasso. CASS is a data correlation dependent method which simultaneously performs automatic data selection and groups correlated data together. It can be regarded as a method which adaptively balances SSC and LSR. Both theoretical and experimental results show the effectiveness of CASS.
3 0.26632968 232 iccv-2013-Latent Space Sparse Subspace Clustering
Author: Vishal M. Patel, Hien Van Nguyen, René Vidal
Abstract: We propose a novel algorithm called Latent Space Sparse Subspace Clustering for simultaneous dimensionality reduction and clustering of data lying in a union of subspaces. Specifically, we describe a method that learns the projection of data and finds the sparse coefficients in the low-dimensional latent space. Cluster labels are then assigned by applying spectral clustering to a similarity matrix built from these sparse coefficients. An efficient optimization method is proposed and its non-linear extensions based on the kernel methods are presented. One of the main advantages of our method is that it is computationally efficient as the sparse coefficients are found in the low-dimensional latent space. Various experiments show that the proposed method performs better than the competitive state-of-theart subspace clustering methods.
4 0.25648779 314 iccv-2013-Perspective Motion Segmentation via Collaborative Clustering
Author: Zhuwen Li, Jiaming Guo, Loong-Fah Cheong, Steven Zhiying Zhou
Abstract: This paper addresses real-world challenges in the motion segmentation problem, including perspective effects, missing data, and unknown number of motions. It first formulates the 3-D motion segmentation from two perspective views as a subspace clustering problem, utilizing the epipolar constraint of an image pair. It then combines the point correspondence information across multiple image frames via a collaborative clustering step, in which tight integration is achieved via a mixed norm optimization scheme. For model selection, wepropose an over-segment and merge approach, where the merging step is based on the property of the ?1-norm ofthe mutual sparse representation oftwo oversegmented groups. The resulting algorithm can deal with incomplete trajectories and perspective effects substantially better than state-of-the-art two-frame and multi-frame methods. Experiments on a 62-clip dataset show the significant superiority of the proposed idea in both segmentation accuracy and model selection.
5 0.24336135 94 iccv-2013-Correntropy Induced L2 Graph for Robust Subspace Clustering
Author: Canyi Lu, Jinhui Tang, Min Lin, Liang Lin, Shuicheng Yan, Zhouchen Lin
Abstract: In this paper, we study the robust subspace clustering problem, which aims to cluster the given possibly noisy data points into their underlying subspaces. A large pool of previous subspace clustering methods focus on the graph construction by different regularization of the representation coefficient. We instead focus on the robustness of the model to non-Gaussian noises. We propose a new robust clustering method by using the correntropy induced metric, which is robust for handling the non-Gaussian and impulsive noises. Also we further extend the method for handling the data with outlier rows/features. The multiplicative form of half-quadratic optimization is used to optimize the nonconvex correntropy objective function of the proposed models. Extensive experiments on face datasets well demonstrate that the proposed methods are more robust to corruptions and occlusions.
6 0.23389523 360 iccv-2013-Robust Subspace Clustering via Half-Quadratic Minimization
7 0.19733933 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
8 0.12071889 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
9 0.10498818 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
10 0.099329911 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
11 0.09800677 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
12 0.090017453 434 iccv-2013-Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition
13 0.085915744 438 iccv-2013-Unsupervised Visual Domain Adaptation Using Subspace Alignment
14 0.075828649 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
15 0.074815251 361 iccv-2013-Robust Trajectory Clustering for Motion Segmentation
16 0.074709594 226 iccv-2013-Joint Subspace Stabilization for Stereoscopic Video
17 0.068965957 310 iccv-2013-Partial Sum Minimization of Singular Values in RPCA for Low-Level Vision
18 0.068579726 392 iccv-2013-Similarity Metric Learning for Face Recognition
19 0.064230964 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
20 0.063694708 357 iccv-2013-Robust Matrix Factorization with Unknown Noise
topicId topicWeight
[(0, 0.17), (1, 0.015), (2, -0.058), (3, -0.01), (4, -0.143), (5, 0.134), (6, 0.01), (7, 0.187), (8, 0.188), (9, -0.008), (10, 0.086), (11, 0.02), (12, -0.164), (13, 0.046), (14, -0.125), (15, -0.054), (16, -0.008), (17, -0.043), (18, -0.019), (19, 0.039), (20, -0.016), (21, 0.157), (22, -0.099), (23, -0.11), (24, -0.009), (25, -0.107), (26, -0.074), (27, 0.039), (28, -0.036), (29, -0.044), (30, -0.007), (31, -0.037), (32, 0.071), (33, -0.023), (34, -0.058), (35, 0.005), (36, -0.029), (37, -0.019), (38, -0.008), (39, 0.03), (40, 0.006), (41, 0.02), (42, -0.024), (43, -0.007), (44, 0.035), (45, -0.052), (46, -0.015), (47, -0.038), (48, 0.01), (49, -0.014)]
simIndex simValue paperId paperTitle
1 0.96284258 93 iccv-2013-Correlation Adaptive Subspace Segmentation by Trace Lasso
Author: Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan
Abstract: This paper studies the subspace segmentation problem. Given a set of data points drawn from a union of subspaces, the goal is to partition them into their underlying subspaces they were drawn from. The spectral clustering method is used as the framework. It requires to find an affinity matrix which is close to block diagonal, with nonzero entries corresponding to the data point pairs from the same subspace. In this work, we argue that both sparsity and the grouping effect are important for subspace segmentation. A sparse affinity matrix tends to be block diagonal, with less connections between data points from different subspaces. The grouping effect ensures that the highly corrected data which are usually from the same subspace can be grouped together. Sparse Subspace Clustering (SSC), by using ?1-minimization, encourages sparsity for data selection, but it lacks of the grouping effect. On the contrary, Low-RankRepresentation (LRR), by rank minimization, and Least Squares Regression (LSR), by ?2-regularization, exhibit strong grouping effect, but they are short in subset selection. Thus the obtained affinity matrix is usually very sparse by SSC, yet very dense by LRR and LSR. In this work, we propose the Correlation Adaptive Subspace Segmentation (CASS) method by using trace Lasso. CASS is a data correlation dependent method which simultaneously performs automatic data selection and groups correlated data together. It can be regarded as a method which adaptively balances SSC and LSR. Both theoretical and experimental results show the effectiveness of CASS.
2 0.94282991 360 iccv-2013-Robust Subspace Clustering via Half-Quadratic Minimization
Author: Yingya Zhang, Zhenan Sun, Ran He, Tieniu Tan
Abstract: Subspace clustering has important and wide applications in computer vision and pattern recognition. It is a challenging task to learn low-dimensional subspace structures due to the possible errors (e.g., noise and corruptions) existing in high-dimensional data. Recent subspace clustering methods usually assume a sparse representation of corrupted errors and correct the errors iteratively. However large corruptions in real-world applications can not be well addressed by these methods. A novel optimization model for robust subspace clustering is proposed in this paper. The objective function of our model mainly includes two parts. The first part aims to achieve a sparse representation of each high-dimensional data point with other data points. The second part aims to maximize the correntropy between a given data point and its low-dimensional representation with other points. Correntropy is a robust measure so that the influence of large corruptions on subspace clustering can be greatly suppressed. An extension of our method with explicit introduction of representation error terms into the model is also proposed. Half-quadratic minimization is provided as an efficient solution to the proposed robust subspace clustering formulations. Experimental results on Hopkins 155 dataset and Extended Yale Database B demonstrate that our method outperforms state-of-the-art subspace clustering methods.
same-paper 3 0.93482697 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
Author: Ameet Talwalkar, Lester Mackey, Yadong Mu, Shih-Fu Chang, Michael I. Jordan
Abstract: Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. In each case, we obtain stateof-the-art results and order-of-magnitude speed ups.
4 0.89221412 94 iccv-2013-Correntropy Induced L2 Graph for Robust Subspace Clustering
Author: Canyi Lu, Jinhui Tang, Min Lin, Liang Lin, Shuicheng Yan, Zhouchen Lin
Abstract: In this paper, we study the robust subspace clustering problem, which aims to cluster the given possibly noisy data points into their underlying subspaces. A large pool of previous subspace clustering methods focus on the graph construction by different regularization of the representation coefficient. We instead focus on the robustness of the model to non-Gaussian noises. We propose a new robust clustering method by using the correntropy induced metric, which is robust for handling the non-Gaussian and impulsive noises. Also we further extend the method for handling the data with outlier rows/features. The multiplicative form of half-quadratic optimization is used to optimize the nonconvex correntropy objective function of the proposed models. Extensive experiments on face datasets well demonstrate that the proposed methods are more robust to corruptions and occlusions.
5 0.88352036 232 iccv-2013-Latent Space Sparse Subspace Clustering
Author: Vishal M. Patel, Hien Van Nguyen, René Vidal
Abstract: We propose a novel algorithm called Latent Space Sparse Subspace Clustering for simultaneous dimensionality reduction and clustering of data lying in a union of subspaces. Specifically, we describe a method that learns the projection of data and finds the sparse coefficients in the low-dimensional latent space. Cluster labels are then assigned by applying spectral clustering to a similarity matrix built from these sparse coefficients. An efficient optimization method is proposed and its non-linear extensions based on the kernel methods are presented. One of the main advantages of our method is that it is computationally efficient as the sparse coefficients are found in the low-dimensional latent space. Various experiments show that the proposed method performs better than the competitive state-of-theart subspace clustering methods.
6 0.85538751 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
7 0.75103444 314 iccv-2013-Perspective Motion Segmentation via Collaborative Clustering
8 0.7395097 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
9 0.72161967 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
10 0.63535303 329 iccv-2013-Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation
11 0.48225427 226 iccv-2013-Joint Subspace Stabilization for Stereoscopic Video
12 0.4615418 235 iccv-2013-Learning Coupled Feature Spaces for Cross-Modal Matching
13 0.4532806 357 iccv-2013-Robust Matrix Factorization with Unknown Noise
14 0.43472469 167 iccv-2013-Finding Causal Interactions in Video Sequences
15 0.39917132 361 iccv-2013-Robust Trajectory Clustering for Motion Segmentation
16 0.39637104 162 iccv-2013-Fast Subspace Search via Grassmannian Based Hashing
17 0.39502516 443 iccv-2013-Video Synopsis by Heterogeneous Multi-source Correlation
18 0.39494652 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
topicId topicWeight
[(2, 0.077), (4, 0.022), (6, 0.01), (7, 0.022), (12, 0.012), (26, 0.088), (27, 0.019), (31, 0.057), (40, 0.01), (42, 0.141), (44, 0.014), (48, 0.016), (64, 0.028), (73, 0.033), (74, 0.139), (78, 0.015), (89, 0.161), (95, 0.012), (98, 0.03)]
simIndex simValue paperId paperTitle
Author: Masakazu Iwamura, Tomokazu Sato, Koichi Kise
Abstract: Approximate nearest neighbor search (ANNS) is a basic and important technique used in many tasks such as object recognition. It involves two processes: selecting nearest neighbor candidates and performing a brute-force search of these candidates. Only the former though has scope for improvement. In most existing methods, it approximates the space by quantization. It then calculates all the distances between the query and all the quantized values (e.g., clusters or bit sequences), and selects a fixed number of candidates close to the query. The performance of the method is evaluated based on accuracy as a function of the number of candidates. This evaluation seems rational but poses a serious problem; it ignores the computational cost of the process of selection. In this paper, we propose a new ANNS method that takes into account costs in the selection process. Whereas existing methods employ computationally expensive techniques such as comparative sort and heap, the proposed method does not. This realizes a significantly more efficient search. We have succeeded in reducing computation times by one-third compared with the state-of-the- art on an experiment using 100 million SIFT features.
same-paper 2 0.89611924 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
Author: Ameet Talwalkar, Lester Mackey, Yadong Mu, Shih-Fu Chang, Michael I. Jordan
Abstract: Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. In each case, we obtain stateof-the-art results and order-of-magnitude speed ups.
3 0.89280051 239 iccv-2013-Learning Hash Codes with Listwise Supervision
Author: Jun Wang, Wei Liu, Andy X. Sun, Yu-Gang Jiang
Abstract: Hashing techniques have been intensively investigated in the design of highly efficient search engines for largescale computer vision applications. Compared with prior approximate nearest neighbor search approaches like treebased indexing, hashing-based search schemes have prominent advantages in terms of both storage and computational efficiencies. Moreover, the procedure of devising hash functions can be easily incorporated into sophisticated machine learning tools, leading to data-dependent and task-specific compact hash codes. Therefore, a number of learning paradigms, ranging from unsupervised to supervised, have been applied to compose appropriate hash functions. How- ever, most of the existing hash function learning methods either treat hash function design as a classification problem or generate binary codes to satisfy pairwise supervision, and have not yet directly optimized the search accuracy. In this paper, we propose to leverage listwise supervision into a principled hash function learning framework. In particular, the ranking information is represented by a set of rank triplets that can be used to assess the quality of ranking. Simple linear projection-based hash functions are solved efficiently through maximizing the ranking quality over the training data. We carry out experiments on large image datasets with size up to one million and compare with the state-of-the-art hashing techniques. The extensive results corroborate that our learned hash codes via listwise supervision can provide superior search accuracy without incurring heavy computational overhead.
4 0.87493169 300 iccv-2013-Optical Flow via Locally Adaptive Fusion of Complementary Data Costs
Author: Tae Hyun Kim, Hee Seok Lee, Kyoung Mu Lee
Abstract: Many state-of-the-art optical flow estimation algorithms optimize the data and regularization terms to solve ill-posed problems. In this paper, in contrast to the conventional optical flow framework that uses a single or fixed data model, we study a novel framework that employs locally varying data term that adaptively combines different multiple types of data models. The locally adaptive data term greatly reduces the matching ambiguity due to the complementary nature of the multiple data models. The optimal number of complementary data models is learnt by minimizing the redundancy among them under the minimum description length constraint (MDL). From these chosen data models, a new optical flow estimation energy model is designed with the weighted sum of the multiple data models, and a convex optimization-based highly effective and practical solution thatfinds the opticalflow, as well as the weights isproposed. Comparative experimental results on the Middlebury optical flow benchmark show that the proposed method using the complementary data models outperforms the state-ofthe art methods.
5 0.86655694 426 iccv-2013-Training Deformable Part Models with Decorrelated Features
Author: Ross Girshick, Jitendra Malik
Abstract: In this paper, we show how to train a deformable part model (DPM) fast—typically in less than 20 minutes, or four times faster than the current fastest method—while maintaining high average precision on the PASCAL VOC datasets. At the core of our approach is “latent LDA,” a novel generalization of linear discriminant analysis for learning latent variable models. Unlike latent SVM, latent LDA uses efficient closed-form updates and does not require an expensive search for hard negative examples. Our approach also acts as a springboard for a detailed experimental study of DPM training. We isolate and quantify the impact of key training factors for the first time (e.g., How important are discriminative SVM filters? How important is joint parameter estimation? How many negative images are needed for training?). Our findings yield useful insights for researchers working with Markov random fields and partbased models, and have practical implications for speeding up tasks such as model selection.
6 0.86180556 427 iccv-2013-Transfer Feature Learning with Joint Distribution Adaptation
7 0.85734367 82 iccv-2013-Compensating for Motion during Direct-Global Separation
8 0.85256344 80 iccv-2013-Collaborative Active Learning of a Kernel Machine Ensemble for Recognition
9 0.85157406 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
10 0.85126388 44 iccv-2013-Adapting Classification Cascades to New Domains
11 0.85055369 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
12 0.85025084 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
13 0.85005808 180 iccv-2013-From Where and How to What We See
14 0.84952271 126 iccv-2013-Dynamic Label Propagation for Semi-supervised Multi-class Multi-label Classification
15 0.84842509 277 iccv-2013-Multi-channel Correlation Filters
16 0.84835392 123 iccv-2013-Domain Adaptive Classification
17 0.84600747 150 iccv-2013-Exemplar Cut
18 0.8457703 161 iccv-2013-Fast Sparsity-Based Orthogonal Dictionary Learning for Image Restoration
19 0.84554046 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
20 0.84551871 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications