nips nips2009 nips2009-147 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raghunandan Keshavan, Andrea Montanari, Sewoong Oh
Abstract: Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the ‘Netflix problem’) to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here O PT S PACE. We prove performance guarantees that are order-optimal in a number of circumstances. 1
Reference: text
sentIndex sentText sentNum sentScore
1 Keshavan∗ Andrea Montanari∗† and Sewoong Oh∗ , , Abstract Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. [sent-2, score-0.23]
2 We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here O PT S PACE. [sent-4, score-0.13]
3 1 Introduction Spectral techniques are an authentic workhorse in machine learning, statistics, numerical analysis, and signal processing. [sent-6, score-0.103]
4 Given a matrix M , its largest singular values –and the associated singular vectors– ‘explain’ the most significant correlations in the underlying data source. [sent-7, score-0.607]
5 In many practical circumstances we have access only to a sparse subset of the entries of an m × n matrix M . [sent-9, score-0.483]
6 It has recently been discovered that, if the matrix M has rank r, and unless it is too ‘structured’, a small random subset of its entries allow to reconstruct it exactly. [sent-10, score-0.628]
7 This result was first proved by Cand´ s and Recht [3] by analyzing a convex relaxation indroduced by Fazel [4]. [sent-11, score-0.21]
8 A tighter e analysis of the same convex relaxation was carried out in [5]. [sent-12, score-0.162]
9 In an alternative line of work, the authors of [1] attacked the same problem using a combination of spectral techniques and manifold optimization: we will refer to their algorithm as O PT S PACE. [sent-14, score-0.167]
10 O PT S PACE is intrinsically of low complexity, the most complex operation being computing r singular values and the corresponding singular vectors of a sparse m × n matrix. [sent-15, score-0.472]
11 The performance guarantees proved in [1] are comparable with the information theoretic lower bound: roughly nr max{r, log n} random entries are needed to reconstruct M exactly (here we assume m of order n). [sent-16, score-0.528]
12 A related approach was also developed in [10], although without performance guarantees for matrix completion. [sent-17, score-0.178]
13 The above results crucially rely on the assumption that M is exactly a rank r matrix. [sent-18, score-0.164]
14 Can the above approaches be generalized when the underlying data is ‘well approximated’ by a rank r matrix? [sent-20, score-0.164]
15 This question was addressed in [11] within the convex relaxation approach of [3]. [sent-21, score-0.162]
16 1 Model definition Let M be an m × n matrix of rank r, that is M = U ΣV T . [sent-25, score-0.299]
17 (1) where U has dimensions m × r, V has dimensions n × r, and Σ is a diagonal r × r matrix. [sent-26, score-0.068]
18 We assume that each entry of M is perturbed, thus producing an ‘approximately’ low-rank matrix N , with Nij = Mij + Zij , (2) where the matrix Z will be assumed to be ‘small’ in an appropriate sense. [sent-27, score-0.317]
19 Out of the m × n entries of N , a subset E ⊆ [m] × [n] is revealed. [sent-28, score-0.293]
20 We let N E be the m × n matrix that contains the revealed entries of N , and is filled with 0’s in the other positions Nij if (i, j) ∈ E , 0 otherwise. [sent-29, score-0.576]
21 The basic idea is to minimize the cost function F (X, Y ), defined by F (X, Y ) ≡ F(X, Y, S) ≡ min F(X, Y, S) , S∈Rr×r 1 2 (i,j)∈E (Nij − (XSY T )ij )2 . [sent-33, score-0.226]
22 The key insight is that the singular value decomposition (SVD) of N E provides an excellent initial guess, and that the minimum can be found with high probability by standard gradient descent after this initialization. [sent-36, score-0.403]
23 Two caveats must be added to this decription: (1) In general the matrix N E must be ‘trimmed’ to eliminate over-represented rows and columns; (2) For technical reasons, we consider a slightly modified cost function to be denoted by F (X, Y ). [sent-37, score-0.179]
24 O PT S PACE( matrix N E ) 1: 2: 3: Trim N E , and let N E be the output; Compute the rank-r projection of N E , Tr (N E ) = X0 S0 Y0T ; Minimize F (X, Y ) through gradient descent, with initial condition (X0 , Y0 ). [sent-38, score-0.22]
25 We may note here that the rank of the matrix M , if not known, can be reliably estimated from N E . [sent-39, score-0.299]
26 We say that a row is ‘over-represented’ if it contains more than 2|E|/m revealed entries (i. [sent-43, score-0.482]
27 more than twice the average number of revealed entries). [sent-45, score-0.218]
28 Analogously, a column is overrepresented if it contains more than 2|E|/n revealed entries. [sent-46, score-0.183]
29 The trimmed matrix N E is obtained from N E by setting to 0 over-represented rows and columns. [sent-47, score-0.262]
30 Let min(m,n) NE = T σi xi yi , i=1 2 (6) be the singular value decomposition of N E , with singular vectors σ1 ≥ σ2 ≥ . [sent-51, score-0.516]
31 We then define Tr (N E ) = mn |E| r T σi xi yi . [sent-55, score-0.283]
32 The modified cost function F is defined as F (X, Y ) = F (X, Y ) + ρ G(X, Y ) m ≡ F (X, Y ) + ρ (8) n (i) 2 ||X || 3µ0 r G1 i=1 +ρ (j) 2 G1 j=1 ||Y || 3µ0 r , (9) where X (i) denotes the i-th row of X, and Y (j) the j-th row of Y . [sent-58, score-0.126]
33 Let us stress that the regularization term is mainly introduced for our proof technique to work (and a broad family of functions G1 would work as well). [sent-63, score-0.113]
34 In numerical experiments we did not find any performance loss in setting ρ = 0. [sent-64, score-0.143]
35 The set of r dimensional subspaces of Rm is a differentiable Riemannian manifold G(m, r) (the Grassman manifold). [sent-67, score-0.14]
36 The gradient descent algorithm is applied to the function F : M(m, n) ≡ G(m, r) × G(n, r) → R. [sent-68, score-0.084]
37 For further details on optimization by gradient descent on matrix manifolds we refer to [12, 13]. [sent-69, score-0.219]
38 Let N = M + Z, where M has rank r and |Mij | ≤ Mmax for all (i, j) ∈ [m] × [n], and assume that the subset of revealed entries E ⊆ [m] × [n] is uniformly random with size |E|. [sent-75, score-0.691]
39 Then there exists numerical constants C and C ′ such that √ 1/2 nrα3/2 1 E ′ n rα √ ||M − Tr (N )||F ≤ CMmax ||Z E ||2 , (10) +C |E| |E| mn with probability larger than 1 − 1/n3 . [sent-76, score-0.518]
40 The key point here is that a much better approximation is obtained by minimizing the cost F (X, Y ) (step 3 in the pseudocode above), provided M satisfies an appropriate incoherence condition. [sent-78, score-0.108]
41 Let M = U ΣV T be a low rank matrix, and assume, without loss of generality, U T U = m1 and V T V = n1. [sent-79, score-0.204]
42 Let N = M + Z, where M is a (µ0 , µ1 )-incoherent matrix of rank r, and assume that the subset of revealed entries E ⊆ [m] × [n] is uniformly random with size |E|. [sent-87, score-0.826]
43 Then there exists numerical constants C and C ′ such that if √ √ (11) |E| ≥ Cn ακ2 max µ0 r α log n ; µ2 r2 ακ4 ; µ2 r2 ακ4 , 0 1 3 then, with probability at least 1 − 1/n3 , √ 1 ′ 2 n αr √ ||M − M ||F ≤ C κ ||Z E ||2 . [sent-90, score-0.409]
44 |E| mn (12) provided that the right-hand side is smaller than Σmin . [sent-91, score-0.283]
45 4 Noise models In order to make sense of the above results, it is convenient to consider a couple of simple models for the noise matrix Z: Independent entries model. [sent-95, score-0.483]
46 We assume that Z’s entries are independent random variables, with zero mean E{Zij } = 0 and sub-gaussian tails. [sent-96, score-0.258]
47 The basic parameter entering our main results is the operator norm of Z E , which is bounded as follows. [sent-100, score-0.104]
48 If Z is a random matrix drawn according to the independent entries model, then there is a constant C such that, √ 1/2 α|E| log |E| ||Z E ||2 ≤ Cσ , (14) n with probability at least 1 − 1/n3 . [sent-103, score-0.434]
49 If Z is a matrix from the worst case model, then 2|E| ||Z E ||2 ≤ √ Zmax , n α (15) for any realization of E. [sent-104, score-0.184]
50 Note that for |E| = Ω(n log n) , no row or column is over-represented with high probability. [sent-105, score-0.082]
51 Then, among the other things, this result implies that for the independent entries model the right-hand side of our error estimate, Eq. [sent-108, score-0.258]
52 Our result however applies to any number of revealed entries, while the one of [14] requires |E| ≥ (8 log n)4 n (which for n ≤ 5 · 108 is larger than n2 ). [sent-116, score-0.224]
53 2, we will mainly compare our algorithm with the convex relaxation approach recently analyzed in [11]. [sent-118, score-0.162]
54 2 0 0 100 200 300 400 500 600 |E|/n Figure 1: Root mean square error achieved by O PT S PACE for reconstructing a random rank-2 matrix, as a function of the number of observed entries |E|, and of the number of line minimizations. [sent-124, score-0.353]
55 The performance of nuclear norm minimization and an information theory lower bound are also shown. [sent-125, score-0.163]
56 Figure 1 compares the average root mean square error for the two algorithms as a function of |E|. [sent-126, score-0.082]
57 Here M is a random rank r = 2 matrix of dimension m = n = 600, generated by letting M = U V T √ with Uij , Vij i. [sent-127, score-0.339]
58 The noise is distributed according to the independent entries model with Zij ∼ N (0, 1). [sent-131, score-0.299]
59 This example is taken from [11] Figure 2, from which we took the data for the convex relaxation approach, as well as the information theory lower bound. [sent-132, score-0.162]
60 After one iteration, O PT S PACE has a smaller root mean square error than [11], and in about 10 iterations it becomes indistiguishable from the information theory lower bound. [sent-133, score-0.082]
61 Let us stress that we require some bound on the condition number κ, while the analysis of [11, 5] requires a stronger incoherence assumption. [sent-135, score-0.154]
62 As far as the error bound is concerned, [11] proved √ 1 ||M − M ||F ≤ 7 mn 2 n ||Z E ||F + √ ||Z E ||F . [sent-136, score-0.37]
63 2 through the operator norm ||Z E ||2 instead of its Frobenius norm ||Z E ||F ≥ ||Z E ||2 . [sent-140, score-0.168]
64 For instance, within the intependent entries model with bounded variance σ, ||Z E ||F = Θ( |E|) while ||Z E ||2 is of order |E|/n (up to logarithmic terms). [sent-142, score-0.258]
65 2 Some notations The matrix M to be reconstructed takes the form (1) where U ∈ Rm×r , V ∈ Rn×r . [sent-143, score-0.223]
66 , vr ] for the columns of the two factors, with ||ui || = m, u T T ||vi || = n, and ui uj = 0, vi vj = 0 for i = j (there is no loss of generality in this, since normalizations can be absorbed by redefining Σ). [sent-150, score-0.148]
67 The maximum and minimum singular values will also be denoted by Σmax = Σ1 and Σmin = Σr . [sent-155, score-0.275]
68 Further, the maximum size of an entry of M is Mmax ≡ maxij |Mij |. [sent-156, score-0.084]
69 Probability is taken with respect to the uniformly random subset E ⊆ [m] × [n] given |E| and (even√ tually) the noise matrix Z. [sent-157, score-0.262]
70 In the case when m = n, ǫ corresponds to the average number of revealed entries per row or column. [sent-159, score-0.482]
71 Then it is√ convenient to work with a model in which each entry is√ revealed independently with probability ǫ/ mn. [sent-160, score-0.279]
72 Since, with high probability √ √ √ |E| ∈ [ǫ α n − A n log n, ǫ α n + A n log n], any guarantee on the algorithm performances that holds within one model, holds within the other model as well if we allow for a vanishing shift in ǫ. [sent-161, score-0.082]
73 For a matrix X ∈ Rn×n , ||X||F is its Frobenius norm, and ||X||2 its operator norm (i. [sent-165, score-0.239]
74 1 As explained in the introduction, the crucial idea is to consider the singular value decomposition of the trimmed matrix N E instead of the original matrix N E . [sent-174, score-0.677]
75 Apart from a trivial rescaling, these singular values are close to the ones of the original matrix M . [sent-175, score-0.371]
76 There exists a numerical constant C such that, with probability greater than 1 − 1/n3 , σq α 1 E − Σq ≤ CMmax + ||Z ||2 , (17) ǫ ǫ ǫ where it is understood that Σq = 0 for q > r. [sent-178, score-0.155]
77 For any matrix A, let σq (A) denote the qth singular value of A. [sent-180, score-0.371]
78 Then, σq (A+B) ≤ σq (A)+ σ1 (B), whence σq − Σq ≤ σq (M E )/ǫ − Σq + σ1 (Z E )/ǫ ǫ α 1 E + ||Z ||2 , ≤ CMmax ǫ ǫ where the second inequality follows from the following Lemma as shown in [1]. [sent-181, score-0.074]
79 There exists a numerical constant C such that, with probability larger than 1 − 1/n3 , √ 1 mn E α √ M− M ≤ CMmax . [sent-184, score-0.438]
80 1) For any matrix A of rank at most 2r, ||A||F ≤ 2r||A||2 , whence √ √ 2r mn 1 E T √ ||M − Tr (N )||F ≤ √ M− NE − σi xi yi ǫ mn mn i≥r+1 2 √ √ √ √ 2r mn E mn E mn ≤ √ M− M + ||Z ||2 + σr+1 ǫ ǫ ǫ mn 2 √ ≤ 2CMmax 2αr/ǫ + (2 2r/ǫ) ||Z E ||2 √ 1/2 √ nrα3/2 n rα ′ ≤ C Mmax +2 2 ||Z E ||2 . [sent-189, score-2.354]
81 2 Recall that the cost function is defined over the Riemannian manifold M(m, n) ≡ G(m, r)×G(n, r). [sent-192, score-0.137]
82 2 consists in controlling the behavior of F in a neighborhood of u = (U, V ) (the point corresponding to the matrix M to be reconstructed). [sent-194, score-0.135]
83 Throughout the proof we let K(µ) be the set of matrix couples (X, Y ) ∈ Rm×r × Rn×r such that ||X (i) ||2 ≤ µr, ||Y (j) ||2 ≤ µr for all i, j 4. [sent-195, score-0.197]
84 , cos θr ) be the T singular values of X1 X2 /m, d(X1 , X2 ) = ||θ||2 . [sent-199, score-0.275]
85 (4), it is also convenient to introduce the notations d− (x, u) ≡ (20) d+ (x, u) ≡ 4. [sent-201, score-0.092]
86 2 Σ2 d(x, u)2 + ||S − Σ||2 , min F Σ2 d(x, u)2 + ||S − Σ||2 . [sent-202, score-0.182]
87 max F (21) Auxiliary lemmas and proof of Theorem 1. [sent-203, score-0.252]
88 2 The proof is based on the following two lemmas that generalize and sharpen analogous bounds in [1] (for proofs we refer to the journal version of this paper). [sent-204, score-0.119]
89 There exists numerical constants C0 , C1 , C2 such that the following happens. [sent-207, score-0.235]
90 Here S ∈ Rr×r is the matrix realizing the minimum in Eq. [sent-210, score-0.174]
91 ǫ Further, for an appropriate choice of the constants in Lemma 4. [sent-216, score-0.08]
92 √ There exists numerical constants C0√C1 , C2 such that the following happens. [sent-220, score-0.235]
93 (22) and (23) we get √ 2 2 F (x) − F (u) ≥ C1 nǫ αΣ2 min d(x, u) − δ0,− , √ 2 2 F (x) − F (u) ≤ C2 nǫ αΣmax d(x, u)2 + δ0,+ , (28) (29) (30) where δ0,− ≡ C √ rΣmax ||Z E ||2 , ǫΣmin Σmin δ0,+ ≡ C √ rΣmax ||Z E ||2 . [sent-235, score-0.182]
94 Indeed without loss of generality we can assume x0 ∈ K(3µ0 ) (because otherwise we can rescale those lines of X0 , Y0 that violate the constraint). [sent-243, score-0.111]
95 max Since√ (xk ) is a non-increasing sequence, the thesis follows provided we take ρ ≥ F C2 nǫ αΣ2 . [sent-246, score-0.172]
96 For all xk such that d(xk , u) ∈ [δ/10, δ], we have F (x) ≥ F (x) ≥ F (x0 ). [sent-252, score-0.141]
97 Since the cost function is twice differentiable, and because of the above, the sequence {xk } converges to Ω = x ∈ K(4µ0 ) ∩ M(m, n) : d(x, u) ≤ δ , grad F (x) = 0 . [sent-254, score-0.164]
98 A singular value thresholding algorithm for matrix come pletion. [sent-296, score-0.371]
99 Fixed point and Bregman iterative methods for matrix rank minimization. [sent-303, score-0.299]
100 An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. [sent-309, score-0.164]
wordName wordTfidf (topN-words)
[('mn', 0.283), ('entries', 0.258), ('singular', 0.236), ('pace', 0.223), ('pt', 0.196), ('revealed', 0.183), ('min', 0.182), ('cmmax', 0.17), ('rank', 0.164), ('zij', 0.159), ('arxiv', 0.154), ('nij', 0.148), ('xk', 0.141), ('matrix', 0.135), ('max', 0.133), ('trimmed', 0.127), ('zmax', 0.127), ('cand', 0.114), ('mmax', 0.111), ('numerical', 0.103), ('mij', 0.102), ('nr', 0.102), ('keshavan', 0.102), ('theorem', 0.101), ('relaxation', 0.1), ('completion', 0.096), ('montanari', 0.095), ('manifold', 0.093), ('grad', 0.085), ('uik', 0.085), ('constants', 0.08), ('rr', 0.08), ('lemma', 0.078), ('whence', 0.074), ('generality', 0.071), ('rm', 0.064), ('tr', 0.064), ('norm', 0.064), ('oh', 0.064), ('incoherence', 0.064), ('convex', 0.062), ('proof', 0.062), ('rn', 0.061), ('frobenius', 0.061), ('nuclear', 0.06), ('reconstructing', 0.06), ('proves', 0.059), ('stanford', 0.057), ('lemmas', 0.057), ('circumstances', 0.055), ('apart', 0.054), ('riemannian', 0.053), ('exists', 0.052), ('stress', 0.051), ('uniformly', 0.051), ('convenient', 0.049), ('worst', 0.049), ('proved', 0.048), ('entry', 0.047), ('subspaces', 0.047), ('root', 0.047), ('projection', 0.045), ('reconstructed', 0.045), ('cost', 0.044), ('decomposition', 0.044), ('descent', 0.044), ('guarantees', 0.043), ('notations', 0.043), ('corollary', 0.041), ('noise', 0.041), ('row', 0.041), ('log', 0.041), ('loss', 0.04), ('letting', 0.04), ('gradient', 0.04), ('operator', 0.04), ('minimum', 0.039), ('bound', 0.039), ('cos', 0.039), ('svd', 0.039), ('thesis', 0.039), ('supu', 0.037), ('vik', 0.037), ('attacked', 0.037), ('maxij', 0.037), ('uij', 0.037), ('arias', 0.037), ('frieze', 0.037), ('normalizations', 0.037), ('raghunandan', 0.037), ('sewoong', 0.037), ('terman', 0.037), ('spectral', 0.037), ('reconstruct', 0.036), ('square', 0.035), ('subset', 0.035), ('preliminary', 0.035), ('twice', 0.035), ('dimensions', 0.034), ('vjk', 0.034)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000006 147 nips-2009-Matrix Completion from Noisy Entries
Author: Raghunandan Keshavan, Andrea Montanari, Sewoong Oh
Abstract: Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the ‘Netflix problem’) to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here O PT S PACE. We prove performance guarantees that are order-optimal in a number of circumstances. 1
Author: John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, Yi Ma
Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the first proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision. 1
3 0.14355926 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers
Author: Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar
Abstract: High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless p/n → 0, a line of recent work has studied models with various types of structure (e.g., sparse vectors; block-structured matrices; low-rank matrices; Markov assumptions). In such settings, a general approach to estimation is to solve a regularized convex program (known as a regularized M -estimator) which combines a loss function (measuring how well the model fits the data) with some regularization function that encourages the assumed structure. The goal of this paper is to provide a unified framework for establishing consistency and convergence rates for such regularized M estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive several existing results, and also to obtain several new results on consistency and convergence rates. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure the corresponding regularized M -estimators have fast convergence rates. 1
4 0.12573583 17 nips-2009-A Sparse Non-Parametric Approach for Single Channel Separation of Known Sounds
Author: Paris Smaragdis, Madhusudana Shashanka, Bhiksha Raj
Abstract: In this paper we present an algorithm for separating mixed sounds from a monophonic recording. Our approach makes use of training data which allows us to learn representations of the types of sounds that compose the mixture. In contrast to popular methods that attempt to extract compact generalizable models for each sound from training data, we employ the training data itself as a representation of the sources in the mixture. We show that mixtures of known sounds can be described as sparse combinations of the training data itself, and in doing so produce significantly better separation results as compared to similar systems based on compact statistical models. Keywords: Example-Based Representation, Signal Separation, Sparse Models. 1
5 0.12149597 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation
Author: Shuheng Zhou
Abstract: Given n noisy samples with p dimensions, where n ≪ p, we show that the multistep thresholding procedure can accurately estimate a sparse vector β ∈ Rp in a linear model, under the restricted eigenvalue conditions (Bickel-Ritov-Tsybakov 09). Thus our conditions for model selection consistency are considerably weaker than what has been achieved in previous works. More importantly, this method allows very significant values of s, which is the number of non-zero elements in the true parameter. For example, it works for cases where the ordinary Lasso would have failed. Finally, we show that if X obeys a uniform uncertainty principle and if the true parameter is sufficiently sparse, the Gauss-Dantzig selector (Cand` se Tao 07) achieves the ℓ2 loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle which would supply perfect information about which coordinates are non-zero and which are above the noise level, while selecting a sufficiently sparse model. 1
6 0.11966299 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms
7 0.11558165 148 nips-2009-Matrix Completion from Power-Law Distributed Samples
8 0.11054885 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models
9 0.086490296 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization
10 0.086415306 1 nips-2009-$L 1$-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry
11 0.084058441 256 nips-2009-Which graphical models are difficult to learn?
12 0.083095565 180 nips-2009-On the Convergence of the Concave-Convex Procedure
13 0.080892608 254 nips-2009-Variational Gaussian-process factor analysis for modeling spatio-temporal data
14 0.07850717 33 nips-2009-Analysis of SVM with Indefinite Kernels
15 0.078355238 144 nips-2009-Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness
16 0.07475213 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem
17 0.071853846 207 nips-2009-Robust Nonparametric Regression with Metric-Space Valued Output
18 0.071423173 64 nips-2009-Data-driven calibration of linear estimators with minimal penalties
19 0.070927486 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors
20 0.066254675 142 nips-2009-Locality-sensitive binary codes from shift-invariant kernels
topicId topicWeight
[(0, -0.225), (1, 0.165), (2, 0.021), (3, 0.089), (4, 0.0), (5, -0.039), (6, 0.073), (7, -0.149), (8, 0.171), (9, 0.019), (10, -0.001), (11, -0.013), (12, 0.036), (13, 0.104), (14, -0.042), (15, -0.046), (16, 0.041), (17, -0.042), (18, -0.152), (19, -0.015), (20, -0.063), (21, 0.01), (22, 0.071), (23, 0.008), (24, -0.054), (25, -0.167), (26, 0.073), (27, -0.198), (28, 0.013), (29, -0.06), (30, 0.014), (31, -0.12), (32, 0.033), (33, -0.068), (34, 0.07), (35, -0.09), (36, 0.044), (37, -0.101), (38, 0.042), (39, 0.146), (40, -0.118), (41, 0.098), (42, 0.1), (43, -0.055), (44, 0.081), (45, 0.112), (46, -0.019), (47, -0.1), (48, -0.048), (49, 0.028)]
simIndex simValue paperId paperTitle
same-paper 1 0.96711344 147 nips-2009-Matrix Completion from Noisy Entries
Author: Raghunandan Keshavan, Andrea Montanari, Sewoong Oh
Abstract: Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the ‘Netflix problem’) to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here O PT S PACE. We prove performance guarantees that are order-optimal in a number of circumstances. 1
Author: John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, Yi Ma
Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the first proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision. 1
3 0.69493872 148 nips-2009-Matrix Completion from Power-Law Distributed Samples
Author: Raghu Meka, Prateek Jain, Inderjit S. Dhillon
Abstract: The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, [4],[13] and [5] obtained the first non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem for more realistic sampling models. Our method is simpler to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easy to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on random instances where the low-rank matrix is sampled according to the prevalent random graph models for complex networks and present promising preliminary results on the Netflix challenge dataset. 1
4 0.63818836 180 nips-2009-On the Convergence of the Concave-Convex Procedure
Author: Gert R. Lanckriet, Bharath K. Sriperumbudur
Abstract: The concave-convex procedure (CCCP) is a majorization-minimization algorithm that solves d.c. (difference of convex functions) programs as a sequence of convex programs. In machine learning, CCCP is extensively used in many learning algorithms like sparse support vector machines (SVMs), transductive SVMs, sparse principal component analysis, etc. Though widely used in many applications, the convergence behavior of CCCP has not gotten a lot of specific attention. Yuille and Rangarajan analyzed its convergence in their original paper, however, we believe the analysis is not complete. Although the convergence of CCCP can be derived from the convergence of the d.c. algorithm (DCA), its proof is more specialized and technical than actually required for the specific case of CCCP. In this paper, we follow a different reasoning and show how Zangwill’s global convergence theory of iterative algorithms provides a natural framework to prove the convergence of CCCP, allowing a more elegant and simple proof. This underlines Zangwill’s theory as a powerful and general framework to deal with the convergence issues of iterative algorithms, after also being used to prove the convergence of algorithms like expectation-maximization, generalized alternating minimization, etc. In this paper, we provide a rigorous analysis of the convergence of CCCP by addressing these questions: (i) When does CCCP find a local minimum or a stationary point of the d.c. program under consideration? (ii) When does the sequence generated by CCCP converge? We also present an open problem on the issue of local convergence of CCCP.
5 0.57996708 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers
Author: Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar
Abstract: High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless p/n → 0, a line of recent work has studied models with various types of structure (e.g., sparse vectors; block-structured matrices; low-rank matrices; Markov assumptions). In such settings, a general approach to estimation is to solve a regularized convex program (known as a regularized M -estimator) which combines a loss function (measuring how well the model fits the data) with some regularization function that encourages the assumed structure. The goal of this paper is to provide a unified framework for establishing consistency and convergence rates for such regularized M estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive several existing results, and also to obtain several new results on consistency and convergence rates. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure the corresponding regularized M -estimators have fast convergence rates. 1
6 0.57563144 33 nips-2009-Analysis of SVM with Indefinite Kernels
7 0.55577374 79 nips-2009-Efficient Recovery of Jointly Sparse Vectors
8 0.54501545 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem
9 0.54337722 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation
10 0.54250008 1 nips-2009-$L 1$-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry
11 0.50444698 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models
12 0.49560353 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms
13 0.46344987 81 nips-2009-Ensemble Nystrom Method
14 0.45673862 185 nips-2009-Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis
15 0.45280939 177 nips-2009-On Learning Rotations
16 0.44508123 140 nips-2009-Linearly constrained Bayesian matrix factorization for blind source separation
17 0.44450998 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors
18 0.42779741 17 nips-2009-A Sparse Non-Parametric Approach for Single Channel Separation of Known Sounds
19 0.42746231 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization
20 0.41947317 138 nips-2009-Learning with Compressible Priors
topicId topicWeight
[(24, 0.085), (25, 0.062), (35, 0.037), (36, 0.094), (39, 0.042), (57, 0.26), (58, 0.199), (61, 0.019), (71, 0.044), (81, 0.022), (86, 0.063), (91, 0.01)]
simIndex simValue paperId paperTitle
1 0.87768829 88 nips-2009-Extending Phase Mechanism to Differential Motion Opponency for Motion Pop-out
Author: Yicong Meng, Bertram E. Shi
Abstract: We extend the concept of phase tuning, a ubiquitous mechanism among sensory neurons including motion and disparity selective neurons, to the motion contrast detection. We demonstrate that the motion contrast can be detected by phase shifts between motion neuronal responses in different spatial regions. By constructing the differential motion opponency in response to motions in two different spatial regions, varying motion contrasts can be detected, where similar motion is detected by zero phase shifts and differences in motion by non-zero phase shifts. The model can exhibit either enhancement or suppression of responses by either different or similar motion in the surrounding. A primary advantage of the model is that the responses are selective to relative motion instead of absolute motion, which could model neurons found in neurophysiological experiments responsible for motion pop-out detection. 1 In trod u ction Motion discontinuity or motion contrast is an important cue for the pop-out of salient moving objects from contextual backgrounds. Although the neural mechanism underlying the motion pop-out detection is still unknown, the center-surround receptive field (RF) organization is considered as a physiological basis responsible for the pop-out detection. The center-surround RF structure is simple and ubiquitous in cortical cells especially in neurons processing motion and color information. Nakayama and Loomis [1] have predicted the existence of motion selective neurons with antagonistic center-surround receptive field organization in 1974. Recent physiological experiments [2][3] show that neurons with center-surround RFs have been found in both middle temporal (MT) and medial superior temporal (MST) areas related to motion processing. This antagonistic mechanism has been suggested to detect motion segmentation [4], figure/ground segregation [5] and the differentiation of object motion from ego-motion [6]. There are many related works [7]-[12] on motion pop-out detection. Some works [7]-[9] are based on spatio-temporal filtering outputs, but motion neurons are not fully interacted by either only inhibiting similar motion [7] or only enhancing opposite motion [8]. Heeger, et al. [7] proposed a center-surround operator to eliminate the response dependence upon rotational motions. But the Heeger's model only shows a complete center-surround interaction for moving directions. With respect to the surrounding speed effects, the neuronal responses are suppressed by the same speed with the center motion but not enhanced by other speeds. Similar problem existed in [8], which only modeled the suppression of neuronal responses in the classical receptive field (CRF) by similar motions in surrounding regions. Physiological experiments [10][11] show that many neurons in visual cortex are sensitive to the motion contrast rather than depend upon the absolute direction and speed of the object motion. Although pooling over motion neurons tuned to different velocities can eliminate the dependence upon absolute velocities, it is computationally inefficient and still can't give full interactions of both suppression and enhancement by similar and opposite surrounding motions. The model proposed by Dellen, et al. [12] computed differential motion responses directly from complex cells in V1 and didn't utilize responses from direction selective neurons. In this paper, we propose an opponency model which directly responds to differential motions by utilizing the phase shift mechanism. Phase tuning is a ubiquitous mechanism in sensory information processing, including motion, disparity and depth detection. Disparity selective neurons in the visual cortex have been found to detect disparities by adjusting the phase shift between the receptive field organizations in the left and right eyes [13][14]. Motion sensitive cells have been modeled in the similar way as the disparity energy neurons and detect image motions by utilizing the phase shift between the real and imaginary parts of temporal complex valued responses, which are comparable to images to the left and right eyes [15]. Therefore, the differential motion can be modeled by exploring the similarity between images from different spatial regions and from different eyes. The remainder of this paper is organized as following. Section 2 illustrates the phase shift motion energy neurons which estimate image velocities by the phase tuning in the imaginary path of the temporal receptive field responses. In section 3, we extend the concept of phase tuning to the construction of differential motion opponency. The phase difference determines the preferred velocity difference between adjacent areas in retinal images. Section 4 investigates properties of motion pop-out detection by the proposed motion opponency model. Finally, in section 5, we relate our proposed model to the neural mechanism of motion integration and motion segmentation in motion related areas and suggest a possible interpretation for adaptive center-surround interactions observed in biological experiments. 2 Phase Shift Motion Energy Neurons Adelson and Bergen [16] proposed the motion energy model for visual motion perception by measuring spatio-temporal orientations of image sequences in space and time. The motion energy model posits that the responses of direction-selective V1 complex cells can be computed by a combination of two linear spatio-temporal filtering stages, followed by squaring and summation. The motion energy model was extended in [15] to be phase tuned by splitting the complex valued temporal responses into real and imaginary paths and adding a phase shift on the imaginary path. Figure 1(a) demonstrates the schematic diagram of the phase shift motion energy model. Here we assume an input image sequence in two-dimensional space (x, y) and time t. The separable spatio-temporal receptive field ensures the cascade implementation of RF with spatial and temporal filters. Due to the requirement of the causal temporal RF, the phase shift motion energy model didn’t adopt the Gabor filter like the spatial RF. The phase shift spatio-temporal RF is modeled with a complex valued function f ( x, y, t ) = g ( x, y ) ⋅ h ( t , Φ ) , where the spatial and temporal RFs are denoted by g ( x, y ) and h ( t , Φ ) respectively, g ( x, y ) = N ( x, y | 0, C ) exp ( jΩ x x + jΩ y y ) h ( t , Φ ) = hreal ( t ) + exp ( jΦ ) himag ( t ) (1) and C is the covariance matrix of the spatial Gaussian envelope and Φ is the phase tuning of the motion energy neuron. The real and imaginary profiles of the temporal receptive field are Gamma modulated sinusoidal functions with quadrature phases, hreal ( t ) = G ( t | α ,τ ) cos ( Ωt t ) (2) himag ( t ) = G ( t | α ,τ ) sin ( Ωt t ) The envelopes for complex exponentials are functions of Gaussian and Gamma distributions, N ( x, y | 0, C ) = ⎛ x2 y2 exp ⎜ − 2 − 2 ⎜ 2σ x 2σ y 2πσ xσ y ⎝ 1 ⎞ ⎟ ⎟ ⎠ (3) hreal (t ) g ( x, y ) himag (t ) g ( x, y ) (·)2 (·)2 M M M (·)2 (·)2 M M M 2 (·) 2 (·) Vreal V (Φ ) e jΦ Vimag (a) Ev ( Φ max ) (·)2 wc ( x, y ) e jΦmin Ev ( (b) M 0 ) w ( x, y ) c M Ev ( Φ min ) M EΔv ( Θ ) ∫∫∫ K x , y ,Φ e j0 e jΦmin ws ( x, y ) Ks c e ∫∫∫ jΘ ws ( x, y ) e j0 x , y ,Φ ws ( x, y ) wc ( x, y ) M e jΦ max e jΦmax (·)2 M (·)2 M M (·)2 M 2 (·) M M (·)2 (c) Figure 1. (a) shows the diagram of the phase shift motion energy model adapted from [15]. (b) draws the spatiotemporal representation of the phase shift motion energy neuron with the real and imaginary receptive field demonstrated by the two left pictures. (c) illustrates the construction of differential motion opponency with a phase difference Θ from two populations of phase shift motion energy neurons in two spatial areas c and s. To avoid clutter, the space location (x, y) is not explicitly shown in phase tuned motion energies. G (t | α ,τ ) = 1 ⎛ t t α −1 exp ⎜ − Γ(α )τ α ⎝ τ ⎞ ⎟ u (t ) ⎠ (4) where Γ (α ) is the gamma function and u ( t ) is the unit step function. The parameters α and τ determine the temporal RF size. As derived in [15], the motion energy at location (x, y) can be computed by E v ( x, y, Φ ) = S + P cos ( Ψ − Φ ) (5) where S = Vreal 2 + Vimag 2 * P = 2 VrealVimag ( * Ψ = arg VrealVimag (6) ) and complex valued responses in real and imaginary paths are obtained as, Vreal ( x, y, t ) = ∫∫∫ g (ξ , ζ ) h (η ) I ( x − ξ , y − ζ , t − η ) dξ dζ dη real ξ ,ζ ,η Vimag ( x, y, t ) = ∫∫∫ g (ξ , ζ ) h (η ) I ( x − ξ , y − ζ , t − η ) dξ dζ dη ξ ζ η (7) imag , , The superscript * represents the complex conjugation and the phase shift parameter Φ controls the spatio-temporal orientation tuning. To avoid clutter, the spatial location variables x and y for S, P, Ψ, Vreal and Vimag are not explicitly shown in Eq. (5) and (6). Figure 1(b) demonstrates the even and odd profiles of the spatio-temporal RF tuned to a particular phase shift. Θ 0 Θ 0 (a) (b) Figure 2. Two types of differential motion opponency constructions of (a) center-surrounding interaction and (b) left-right interaction. Among cells in area MT with surrounding modulations, 25% of cells are with the antagonistic RF structure in the top row and another 50% of cells have the integrative RF structure as shown in the bottom row. 3 Extending Phase Op p on ency Mechanism to D i f f e r e nt i a l Motion Based on the above phase shift motion energy model, the local image velocity at each spatial location can be represented by a phase shift which leads to the peak response across a population of motion energy neurons. Across regions of different motions, there are clear discontinuities on the estimated velocity map. The motion discontinuities can be detected by edge detectors on the velocity map to segment different motions. However, this algorithm for motion discontinuities detection can’t discriminate between the object motion and uniform motions in contextual backgrounds. Here we propose a phase mechanism to detect differential motions inspired by the disparity energy model and adopt the center-surround inhibition mechanism to pop out the object motion from contextual background motions. The motion differences between different spatial locations can be modeled in the similar way as the disparity model. The motion energies from two neighboring locations are considered as the retinal images to the left and right eyes. Thus, we can construct a differential motion opponency by placing two populations of phase shift motion energy neurons at different spatial locations and the energy EΔv ( Θ ) of the opponency is the squared modulus of the averaged phase shift motion energies over space and phase, E Δv ( Θ ) = ∫∫∫ E ( x, y, Φ ) ⋅ w ( x, y, Φ | Θ ) dxdyd Φ v 2 (8) where w ( x, y, Θ ) is the profile for differential motion opponency and Δv is the velocity difference between the two spatial regions defined by the kernel w ( x, y, Θ ) . Since w ( x, y, Θ ) is intended to implement the functional role of spatial interactions, it is desired to be a separable function in space and phase domain and can be modeled by phase tuned summation of two spatial kernels, w ( x, y, Φ | Θ ) = wc ( x, y ) e jΦ + e jΘ+ jΦ ws ( x, y ) (9) where wc ( x, y ) and ws ( x, y ) are Gaussian kernels of different spatial sizes σ c and σ s , and Θ is the phase difference representing velocity difference between two spatial regions c and s. Substituting Eq. (9) into Eq. (8), the differential motion energy can be reformulated as EΔv ( Θ ) = K c + e jΘ K s 2 (10) 3 3 3 2 2 2 1 1 1 0 0 -1 -1 -2 -2 -2 -3 -3 -3 -3 -3 1 Right Velocity Right Velocity 0.98 0.96 0.94 0.92 0 0.9 0.88 -1 0.86 0.84 0.82 -2 -1 0 1 Left Velocity 2 3 -2 -1 0 1 Left Velocity 2 3 0.8 (a) (b) Figure 3. (a) Phase map and (b) peak magnitude map are obtained from stimuli of two patches of random dots moving with different velocities. The two patches of stimuli are statistically independent but share the same spatial properties: dot size of 2 pixels, dot density of 10% and dot coherence level of 100%. The phase tuned population of motion energy neurons are applied to each patch of random dots with RF parameters: Ωt = 2π/8, Ωt = 2π/16, σx = 5 and τ = 5.5. For each combination of velocities from left and right patches, averaged phase shifts over space and time are computed and so do the magnitudes of peak responses. The unit for velocities is pixels per frame. where Kc = ∫∫∫ E ( x, y, Φ ) exp ( jΦ ) w ( x, y ) dxdyd Φ v,c c x , y ,Φ Ks = ∫∫∫ E ( x, y, Φ ) exp ( jΦ ) w ( x, y ) dxdyd Φ v,s (11) s x, y ,Φ Ev ,c ( x, y, Φ ) and Ev , s ( x, y, Φ ) are phase shift motion energies at location (x, y) and with phase shift Φ. Utilizing the results in Eq. (5) and (6), Eq. (10) and (11) generate similar results, E Δv ( Θ ) = Sopp + Popp cos ( Θopp − Θ ) (12) where Sopp = K c 2 + Ks Popp = 2 K c K s* 2 (13) Θopp = arg ( K c K s* ) According to above derivations, by varying the phase shift Θ between –π and π, the relative motion energy of the differential motion opponency can be modeled as population responses across a population of phase tuned motion opponencies. The response is completely specified by three parameters Sopp , Popp and Θopp . The schematic diagram of this opponency is illustrated in Figure 1(c). The differential motion opponency is constituted by three stages. At the first stage, a population of phase shift motion energy neurons is applied to be selective to different velocities. At the second stage, motion energies from the first stage are weighted by kernels tuned to different spatial locations and phase shifts respectively for both spatial regions and two single differential motion signals in region c and region s are achieved by integrating responses from these two regions over space and phase tuning. Finally, the differential motion energy is computed by the squared modulus of the summation of the integrated motion signal in region c and phase shifted motion signal in region s. The subscripts c and s represent two interacted spatial regions which are not limited to the center and surround regions. The opponency could also be constructed by the neighboring left and right Inhibitive interaction, Θ = π/2 Excitatory interaction, Θ =0 Inhibitory 2 1.6 Responses 1.6 Responses Excitatory 2 1.2 0.8 1.2 0.8 0.4 0.4 0 0 pi/2 pi 3pi/2 Surrouding Direction 0 0 2pi (a) Model by Petkov et al. [8] pi/2 pi 3pi/2 Surrouding Direction (b) Model by Heeger et al. [7] Inhibitory 2 2pi Inhibitory 2 1.6 1.6 Responses Responses 1.2 0.8 1.2 0.8 0.4 0.4 0 0 0 pi/2 pi Surrouding Direction 3pi/2 2pi 0 pi/2 pi Surrouding Direction 3pi/2 2pi (c) (d) Figure 4. Demonstrations of center-surround differential motion opponency, where (a) show the excitation of opposite directions outside the CRF and (b) show the inhibition by surrounding motions in same directions. The center-surround inhibition models by Petkov, et al. [8] and Heeger, et al. [7] are shown in (c) and (d). Responses above 1 indicate enhancement and responses below 1 indicate suppressions. spatial regions. Figure 2 shows two types of structures for the differential motion opponency. In [17], the authors demonstrates that among cells in area MT with surrounding modulations, 25% of cells are with the antagonistic RF structure as shown in Figure 2(a) and another 50% of cells have the integrative RF structure as shown in Figure 2(b). The velocity difference tuning of the opponency is determined by the phase shift parameter Θ combined with parameters of spatial and temporal frequencies for motion energy neurons. The larger phase shift magnitude prefers the bigger velocity difference. This phase tuning of velocity difference is consistent with the phase tuning of motion energy neurons. Figure 3 shows the phase map obtained by using random dots stimuli with different velocities on two spatial patches (left and right patches with sizes of 128 pixels 128 pixels). Along the diagonal line, velocities from left and right patches are equal to each other and therefore phase estimates are zeros along this line. Deviated from the diagonal line to upper-left and lower-right, the phase magnitudes increase while positive phases indicate larger left velocities and negative phases indicate larger right velocities. The phase tuning can give a good classification of velocity differences. 4 V a l i d a t i o n o f D i f f e r e n t i a l M o t i o n O pp o n e n c y Out derivation and analysis above show that the phase shift between two neighboring spatial regions is a good indicator for motion difference between these two regions. In this section, we validate the proposed differential motion opponency by two sets of experiments, which show effects of both surrounding directions and speeds on the center motion. Inhibitory 2 1.6 1.2 1.2 Responses 1.6 Responses Inhibitory 2 0.8 0.4 0.4 0 -2 0.8 0 -1.5 -1 -0.5 0 0.5 Center Speed 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 Center Speed 1 1.5 2 (a) (b) Figure 5. The insensitivity of the proposed opponency model to absolute center and surrounding velocities is demonstrated in (a), where responses are enhanced for all center velocities from -2 to 2 pixels per frame. In (b), the model by Heeger, et al. [7] only shows enhancement when the center speed matches the preferred speed of 1.2 pixel per frame. Similarly, responses above 1 indicate enhancement and below 1 indicate suppressions. In both curves, the velocity differences between center and surrounding regions are maintained as a constant of 3 pixels per frame. Physiological experiments [2][3] have demonstrated that the neuronal activities in the classical receptive field are suppressed by responses outside the CRF to stimuli with similar motions including both directions and speeds on the center and surrounding regions. On the contrary, visual stimuli of opposite directions or quite different speeds outside the CRF enhance the responses in the CRF. In their experiments, they used a set of stimuli of random dots moving at different velocities, where there are small patches of moving random dots on the center. We tested the properties of the proposed opponency model for motion difference measurement by using similar random dots stimuli. The random dots on background move with different speeds and in different direction but have the same statistical parameters: dot size of 2 pixels, dot density of 10% and motion coherence level of 100%. The small random dots patches are placed on the center of background stimuli to stimulate the neurons in the CRF. These small patches share the same statistical parameters with background random dots but move with a constant velocity of 1 pixel per frame. Figure 4 shows results for the enhanced and suppressed responses in the CRF with varying surrounding directions. The phase shift motion energy neurons had the same spatial and temporal frequencies and the same receptive field sizes, and were selective to vertical orientations. The preferred spatial frequency was 2π/16 radian per pixel and the temporal frequency was 2π/16 radian per frame. The sizes of RF in horizontal and vertical directions were respectively 5 pixels and 10 pixels, corresponding to a spatial bandwidth of 1.96 octaves. The time constant τ was 5.5 frames which resulted in a temporal bandwidth of 1.96 octaves. As shown in Figure 4 (a) and (b), the surrounding motion of opposite direction gives the largest response to the motion in the CRF for the inhibitory interaction and the smallest response for the excitatory interaction. Results demonstrated in Figure 4 are consistent with physiological results reported in [3]. In Born’s paper, inhibitory cells show response enhancement and excitatory cells show response suppression when surrounding motions are in opposite directions. The 3-dB bandwidth for the surrounding moving direction is about 135 degrees for the physiological experiments while the bandwidth is about 180 degrees for the simulation results in our proposed model. Models proposed by Petkov, et al. [8] and Heeger, et al. [7] also show clear inhibition between opposite motions. The Petkov’s model achieves the surrounding suppression for each point in ( x, y, t ) space by the subtraction between responses from that point and its surroundings and followed by a half-wave rectification, + % Ev ,θ ( x, y, t ) = Ev ,θ ( x, y, t ) − α ⋅ Sv ,θ ( x, y, t ) (14) where Ev ,θ ( x, y, t ) is the motion energy at location (x,y) and time t for a given preferred speed v and orientation θ, Sv ,θ ( x, y, t ) is the average motion energy in the surrounding of point (x, y, t), % Ev ,θ ( x, y, t ) is the suppressed motion energy and the factor α controls the inhibition strength. The inhibition term is computed by weighted motion energy Sv ,θ ( x, y, t ) = Ev ,θ ( x, y, t ) ∗ wv ,θ ( x, y, t ) (15) where wv ,θ ( x, y, t ) is the surround weighting function. The Heeger’s model constructs the center-surround motion opponent by computing the weighted sum of responses from motion selective cells, Rv ,θ ( t ) = ∑ β ( x, y ) ⎡ Ev ,θ ( x, y, t ) − E− v ,θ ( x, y, t ) ⎤ ⎣ ⎦ (16) x, y where β ( x, y ) is a center-surround weighting function and the motion energy at each point should be normalized across all cells with different tuning properties. As shown in Figure 4 (c) and (d) for results of Petkov’s and Heeger’s models, we replace the conventional frequency tuned motion energy neuron with our proposed phase tuned neuron. The model by Petkov, et al. [8] is generally suppressive and only reproduces less suppression for opposite motions, which is inconsistent with results from [3]. The model by Heeger, et al. [7] has similar properties with our proposed model with respect to both excitatory and inhibitory interactions. To evaluate the sensitivity of the proposed opponency model to velocity differences, we did simulations by using similar stimuli with the above experiment in Figure 4 but maintaining a constant velocity difference of 3 pixels per frame between the center and surrounding random dot patches. As shown in Figure 5, by varying the velocities of random dots on the center region, we found that responses by the proposed model are always enhanced independent upon absolute velocities of center stimuli, but responses by the Heeger’s model achieve the enhancement at a center velocity of 1.2 pixels per frame and maintain suppressed at other speeds. 5 D i s c u s s i on We proposed a new biologically plausible model of the differential motion opponency to model the spatial interaction property of motion energy neurons. The proposed opponency model is motivated by the phase tuning mechanism of disparity energy neurons which infers the disparity information from the phase difference between complex valued responses to left and right retinal images. Hence, the two neighboring spatial areas can be considered as left and right images and the motion difference between these two spatial regions is detected by the phase difference between the complex valued responses at these two regions. Our experimental results demonstrate a consistent conclusion with physiological experiments that motions of opposite directions and different speeds outside the CRF can show both inhibitive and excitatory effects on the CRF responses. The inhibitive interaction helps to segment the moving object from backgrounds when fed back to low-level features such as edges, orientations and color information. Except providing a unifying phase mechanism in understanding neurons with different functional roles at different brain areas, the proposed opponency model could possibly provide a way to understand the motion integration and motion segmentation. Integration and segmentation are two opposite motion perception tasks but co-exist to constitute two fundamental types of motion processing. Segmentation is achieved by discriminating motion signals from different objects, which is thought to be due to the antagonistic interaction between center and surrounding RFs. Integration is obtained by utilizing the enhancing function of surrounding areas to CRF areas. Both types of processing have been found in motion related areas including area MT and MST. Tadin, et al. [18] have found that motion segmentation dominants at high stimulus contrast and gives the way to motion integration at low stimulus contrast. Huang, et al. [19] suggests that the surrounding modulation is adaptive according to the visual stimulus such as contrasts and noise levels. Since our proposed opponency model determines the functional role of neurons by only the phase shift parameter, this makes the proposed model to be an ideal candidate model for the adaptive surrounding modulation with the phase tuning between two spatial regions. References [1]. K. Nakayama and J. M. Loomis, “Optical velocity patterns, velocity-sensitive neurons, and space perception: A hypothesis,” Perception, vol. 3, 63-80, 1974. [2]. K. Tanaka, K. Hikosaka, H. Saito, M. Yukie, Y. Fukada and E. Iwai, “Analysis of local and wide-field movements in the superior temporal visual areas of the macaque monkey,” Journal of Neuroscience, vol. 6, pp. 134-144, 1986. [3]. R. T. Born and R. B. H. Tootell, “Segregation of global and local motion processing in primate middle temporal visual area,” Nature, vol. 357, pp. 497-499, 1992. [4]. J. Allman, F. Miezin and E. McGuinness, “Stimulus specific responses from beyond the classical receptive field: Neurophysiological mechanisms for local-global comparisions in visual neurons,” Annual Review Neuroscience, vol. 8, pp. 407-430, 1985. [5]. V. A. F. Lamme, “The neurophysiology of figure-ground segregation in primary visual cortex,” Journal of Neuroscience, vol. 15, pp. 1605-1615, 1995. [6]. D. C. Bradley and R. A. Andersen, “Center-surround antagonism based on disparity in primate area MT,” Journal of Neuroscience, vol. 18, pp. 7552-65, 1998. [7]. D. J. Heeger, A. D. Jepson and E. P. Simoncelli, “Recovering observer translation with center-surround operators,” Proc IEEE Workshop on Visual Motion, pp. 95-100, Oct 1991. [8]. N. Petkov and E. Subramanian, “Motion detection, noise reduction, texture suppression, and contour enhancement by spatiotemporal Gabor filters with surround inhibition,” Biological Cybernetics, vol. 97, pp. 423-439, 2007. [9]. M. Escobar and P. Kornprobst, “Action recognition with a Bio-inspired feedforward motion processing model: the richness of center-surround interactions,” ECCV '08: Proceedings of the 10th European Conference on Computer Vision, pp. 186-199, Marseille, France, 2008. [10]. B. J. Frost and K. Nakayama, “Single visual neurons code opposing motion independent of direction,” Science, vol. 200, pp. 744-745, 1983. [11]. A. Cao and P. H. Schiller, “Neural responses to relative speed in the primary visual cortex of rhesus monkey,” Visual Neuroscience, vol. 20, pp. 77-84, 2003. [12]. B. K. Dellen, J. W. Clark and R. Wessel, “Computing relative motion with complex cells,” Visual Neuroscience, vol. 22, pp. 225-236, 2005. [13]. I. Ohzawa, G. C. Deangelis and R. D. Freeman, “Encoding of binocular disparity by complex cells in the cat’s visual cortex,” Journal of Neurophysiology, vol. 77, pp. 2879-2909, 1997. [14]. D. J. Fleet, H. Wagner and D. J. Heeger, “Neural Encoding of binocular disparity: energy model, position shifts and phase shifts,” Vision Research, vol. 26, pp. 1839-1857, 1996. [15]. Y. C. Meng and B. E. Shi, “Normalized Phase Shift Motion Energy Neuron Populations for Image Velocity Estimation,” International Joint Conference on Neural Network, Atlanta, GA, June 14-19, 2009. [16]. E. H. Adelson and J. R. Bergen, “Spatiotemporal energy models for the perception of motion,” J. Opt. Soc. Am. A Opt. Image Sci. Vis., vol. 2, pp. 284-299, 1985. [17]. D. K. Xiao, S. Raiguel, V. Marcar, J. Koenderink and G. A. Orban, “The spatial distribution of the antagonistic surround of MT/V5,” Cereb Cortex, vol. 7, pp. 662-677, 1997. [18]. D. Tadin, J. S. Lappin, L. A. Gilroy and R. Blake, “Perceptual consequences of centre-surround antagonism in visual motion processing,” Nature, vol. 424, pp. 312-315, 2003. [19]. X. Huang, T. D. Albright and G. R. Stoner, “Adaptive surround modulation in cortical area MT,” Neuron, vol. 53, pp. 761-770, 2007.
2 0.84246939 232 nips-2009-Strategy Grafting in Extensive Games
Author: Kevin Waugh, Nolan Bard, Michael Bowling
Abstract: Extensive games are often used to model the interactions of multiple agents within an environment. Much recent work has focused on increasing the size of an extensive game that can be feasibly solved. Despite these improvements, many interesting games are still too large for such techniques. A common approach for computing strategies in these large games is to first employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size. This abstract game is then solved and the resulting strategy is played in the original game. Most top programs in recent AAAI Computer Poker Competitions use this approach. The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games. These larger abstract games have more expressive strategy spaces and therefore contain better strategies. In this paper we present a new method for computing strategies in large games. This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve. We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justification for the resulting improvement. 1
3 0.83850014 138 nips-2009-Learning with Compressible Priors
Author: Volkan Cevher
Abstract: We describe a set of probability distributions, dubbed compressible priors, whose independent and identically distributed (iid) realizations result in p-compressible signals. A signal x ∈ RN is called p-compressible with magnitude R if its sorted coefficients exhibit a power-law decay as |x|(i) R · i−d , where the decay rate d is equal to 1/p. p-compressible signals live close to K-sparse signals (K N) in the r -norm (r > p) since their best K-sparse approximation error decreases with O R · K 1/r−1/p . We show that the membership of generalized Pareto, Student’s t, log-normal, Fr´ chet, and log-logistic distributions to the set of compresse ible priors depends only on the distribution parameters and is independent of N . In contrast, we demonstrate that the membership of the generalized Gaussian distribution (GGD) depends both on the signal dimension and the GGD parameters: the expected decay rate of N -sample iid realizations from the GGD with the shape parameter q is given by 1/ [q log (N/q)]. As stylized examples, we show via experiments that the wavelet coefficients of natural images are 1.67-compressible whereas their pixel gradients are 0.95 log (N/0.95)-compressible, on the average. We also leverage the connections between compressible priors and sparse signals to develop new iterative re-weighted sparse signal recovery algorithms that outperform the standard 1 -norm minimization. Finally, we describe how to learn the hyperparameters of compressible priors in underdetermined regression problems by exploiting the geometry of their order statistics during signal recovery. 1
same-paper 4 0.83245617 147 nips-2009-Matrix Completion from Noisy Entries
Author: Raghunandan Keshavan, Andrea Montanari, Sewoong Oh
Abstract: Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the ‘Netflix problem’) to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here O PT S PACE. We prove performance guarantees that are order-optimal in a number of circumstances. 1
5 0.69641119 243 nips-2009-The Ordered Residual Kernel for Robust Motion Subspace Clustering
Author: Tat-jun Chin, Hanzi Wang, David Suter
Abstract: We present a novel and highly effective approach for multi-body motion segmentation. Drawing inspiration from robust statistical model fitting, we estimate putative subspace hypotheses from the data. However, instead of ranking them we encapsulate the hypotheses in a novel Mercer kernel which elicits the potential of two point trajectories to have emerged from the same subspace. The kernel permits the application of well-established statistical learning methods for effective outlier rejection, automatic recovery of the number of motions and accurate segmentation of the point trajectories. The method operates well under severe outliers arising from spurious trajectories or mistracks. Detailed experiments on a recent benchmark dataset (Hopkins 155) show that our method is superior to other stateof-the-art approaches in terms of recovering the number of motions, segmentation accuracy, robustness against gross outliers and computational efficiency. 1 Introduction1 Multi-body motion segmentation concerns the separation of motions arising from multiple moving objects in a video sequence. The input data is usually a set of points on the surface of the objects which are tracked throughout the video sequence. Motion segmentation can serve as a useful preprocessing step for many computer vision applications. In recent years the case of rigid (i.e. nonarticulated) objects for which the motions could be semi-dependent on each other has received much attention [18, 14, 19, 21, 22, 17]. Under this domain the affine projection model is usually adopted. Such a model implies that the point trajectories from a particular motion lie on a linear subspace of at most four, and trajectories from different motions lie on distinct subspaces. Thus multi-body motion segmentation is reduced to the problem of subspace segmentation or clustering. To realize practical algorithms, motion segmentation approaches should possess four desirable attributes: (1) Accuracy in classifying the point trajectories to the motions they respectively belong to. This is crucial for success in the subsequent vision applications, e.g. object recognition, 3D reconstruction. (2) Robustness against inlier noise (e.g. slight localization error) and gross outliers (e.g. mistracks, spurious trajectories), since getting imperfect data is almost always unavoidable in practical circumstances. (3) Ability to automatically deduce the number of motions in the data. This is pivotal to accomplish fully automated vision applications. (4) Computational efficiency. This is integral for the processing of video sequences which are usually large amounts of data. Recent work on multi-body motion segmentation can roughly be divided into algebraic or factorization methods [3, 19, 20], statistical methods [17, 7, 14, 6, 10] and clustering methods [22, 21, 5]. Notable approaches include Generalized PCA (GPCA) [19, 20], an algebraic method based on the idea that one can fit a union of m subspaces with a set of polynomials of degree m. Statistical methods often employ concepts such random hypothesis generation [4, 17], Expectation-Maximization [14, 6] 1 This work was supported by the Australian Research Council (ARC) under the project DP0878801. 1 and geometric model selection [7, 8]. Clustering based methods [22, 21, 5] are also gaining attention due to their effectiveness. They usually include a dimensionality reduction step (e.g. manifold learning [5]) followed by a clustering of the point trajectories (e.g. via spectral clustering in [21]). A recent benchmark [18] indicated that Local Subspace Affinity (LSA) [21] gave the best performance in terms of classification accuracy, although their result was subsequently surpassed by [5, 10]. However, we argue that most of the previous approaches do not simultaneously fulfil the qualities desirable of motion segmentation algorithms. Most notably, although some of the approaches have the means to estimate the number of motions, they are generally unreliable in this respect and require manual input of this parameter. In fact this prior knowledge was given to all the methods compared in [18]2 . Secondly, most of the methods (e.g. [19, 5]) do not explicitly deal with outliers. They will almost always breakdown when given corrupted data. These deficiencies reduce the usefulness of available motion segmentation algorithms in practical circumstances. In this paper we attempt to bridge the gap between experimental performance and practical usability. Our previous work [2] indicates that robust multi-structure model fitting can be achieved effectively with statistical learning. Here we extend this concept to motion subspace clustering. Drawing inspiration from robust statistical model fitting [4], we estimate random hypotheses of motion subspaces in the data. However, instead of ranking these hypotheses we encapsulate them in a novel Mercer kernel. The kernel can function reliably despite overwhelming sampling imbalance, and it permits the application of non-linear dimensionality reduction techniques to effectively identify and reject outlying trajectories. This is then followed by Kernel PCA [11] to maximize the separation between groups and spectral clustering [13] to recover the number of motions and clustering. Experiments on the Hopkins 155 benchmark dataset [18] show that our method is superior to other approaches in terms of the qualities described above, including computational efficiency. 1.1 Brief review of affine model multi-body motion segmentation Let {tf p ∈ R2 }f =1,...,F be the set of 2D coordinates of P trajectories tracked across F frames. In p=1,...,P multi-body motion segmentation the tf p ’s correspond to points on the surface of rigid objects which are moving. The goal is to separate the trajectories into groups corresponding to the motion they belong to. In other words, if we arrange the coordinates in the following data matrix t11 · · · t1P . . ∈ R2F ×P , .. . T= . (1) . . . tF 1 . . . tF P the goal is to find the permutation Γ ∈ RP ×P such that the columns of T · Γ are arranged according to the respective motions they belong to. It turns out that under affine projection [1, 16] trajectories from the same motion lie on a distinct subspace in R2F , and each of these motion subspaces is of dimensions 2, 3 or 4. Thus motion segmentation can be accomplished via clustering subspaces in R2F . See [1, 16] for more details. Realistically actual motion sequences might contain trajectories which do not correspond to valid objects or motions. These trajectories behave as outliers in the data and, if not taken into account, can be seriously detrimental to subspace clustering algorithms. 2 The Ordered Residual Kernel (ORK) First, we take a statistical model fitting point of view to motion segmentation. Let {xi }i=1,...,N be the set of N samples on which we want to perform model fitting. We randomly draw p-subsets from the data and use it to fit a hypothesis of the model, where p is the number of parameters that define the model. In motion segmentation, the xi ’s are the columns of matrix T, and p = 4 since the model is a four-dimensional subspace3 . Assume that M of such random hypotheses are drawn. i i For each data point xi compute its absolute residual set ri = {r1 , . . . , rM } as measured to the M hypotheses. For motion segmentation, the residual is the orthogonal distance to a hypothesis 2 As confirmed through private contact with the authors of [18]. Ideally we should also consider degenerate motions with subspace dimensions 2 or 3, but previous work [18] using RANSAC [4] and our results suggest this is not a pressing issue for the Hopkins 155 dataset. 3 2 i i subspace. We sort the elements in ri to obtain the sorted residual set ˜i = {rλi , . . . , rλi }, where r 1 M i i the permutation {λi , . . . , λi } is obtained such that rλi ≤ · · · ≤ rλi . Define the following 1 M 1 M ˜ θi := {λi , . . . , λi } 1 M (2) ˜ as the sorted hypothesis set of point xi , i.e. θi depicts the order in which xi becomes the inlier of the M hypotheses as a fictitious inlier threshold is increased from 0 to ∞. We define the Ordered Residual Kernel (ORK) between two data points as 1 kr (xi1 , xi2 ) := ˜ Z M/h t ˜ ˜ zt · k∩ (θi1 , θi2 ), (3) t=1 M/h where zt = 1 are the harmonic series and Z = t=1 zt is the (M/h)-th harmonic number. t Without lost of generality assume that M is wholly divisible by h. Step size h is used to obtain the Difference of Intersection Kernel (DOIK) 1 ˜1:α t ˜ ˜ ˜1:α ˜1:α ˜1:α k∩ (θi1 , θi2 ) := (|θi1 t ∩ θi2 t | − |θi1 t−1 ∩ θi2 t−1 |) (4) h ˜a:b where αt = t · h and αt−1 = (t − 1) · h. Symbol θi indicates the set formed by the a-th to ˜i . Since the contents of the sorted hypotheses set are merely permutations of the b-th elements of θ {1 . . . M }, i.e. there are no repeating elements, 0 ≤ kr (xi1 , xi2 ) ≤ 1. ˜ (5) Note that kr is independent of the type of model to be fitted, thus it is applicable to generic statistical ˜ model fitting problems. However, we concentrate on motion subspaces in this paper. Let τ be a fictitious inlier threshold. The kernel kr captures the intuition that, if τ is low, two ˜ points arising from the same subspace will have high normalized intersection since they share many common hypotheses which correspond to that subspace. If τ is high, implausible hypotheses fitted on outliers start to dominate and decrease the normalized intersection. Step size h allows us to quantify the rate of change of intersection if τ is increased from 0 to ∞, and since zt is decreasing, kr will evaluate to a high value for two points from the same subspace. In contrast, kr is always low ˜ ˜ for points not from the same subspace or that are outliers. Proof of satisfying Mercer’s condition. Let D be a fixed domain, and P(D) be the power set of D, i.e. the set of all subsets of D. Let S ⊆ P(D), and p, q ∈ S. If µ is a measure on D, then k∩ (p, q) = µ(p ∩ q), (6) called the intersection kernel, is provably a valid Mercer kernel [12]. The DOIK can be rewritten as t ˜ ˜ k∩ (θi1 , θi2 ) = 1 ˜(αt−1 +1):αt ˜(αt−1 +1):αt (|θ ∩ θi2 | h i1 ˜1:(α ) ˜(α +1):αt | + |θ (αt−1 +1):αt ∩ θ 1:(αt−1 ) |). ˜ ˜ +|θi1 t−1 ∩ θi2 t−1 i1 i2 (7) If we let D = {1 . . . M } be the set of all possible hypothesis indices and µ be uniform on D, each term in Eq. (7) is simply an intersection kernel multiplied by |D|/h. Since multiplying a kernel with a positive constant and adding two kernels respectively produce valid Mercer kernels [12], the DOIK and ORK are also valid Mercer kernels.• Parameter h in kr depends on the number of random hypotheses M , i.e. step size h can be set as a ˜ ratio of M . The value of M can be determined based on the size of the p-subset and the size of the data N (e.g. [23, 15]), and thus h is not contingent on knowledge of the true inlier noise scale or threshold. Moreover, our experiments in Sec. 4 show that segmentation performance is relatively insensitive to the settings of h and M . 2.1 Performance under sampling imbalance Methods based on random sampling (e.g. RANSAC [4]) are usually affected by unbalanced datasets. The probability of simultaneously retrieving p inliers from a particular structure is tiny if points 3 from that structure represent only a small minority in the data. In an unbalanced dataset the “pure” p-subsets in the M randomly drawn samples will be dominated by points from the majority structure in the data. This is a pronounced problem in motion sequences, since there is usually a background “object” whose point trajectories form a large majority in the data. In fact, for motion sequences from the Hopkins 155 dataset [18] with typically about 300 points per sequence, M has to be raised to about 20,000 before a pure p-subset from the non-background objects is sampled. However, ORK can function reliably despite serious sampling imbalance. This is because points from the same subspace are roughly equi-distance to the sampled hypotheses in their vicinity, even though these hypotheses might not pass through that subspace. Moreover, since zt in Eq. (3) is decreasing only residuals/hypotheses in the vicinity of a point are heavily weighted in the intersection. Fig. 1(a) illustrates this condition. Results in Sec. 4 show that ORK excelled even with M = 1, 000. (a) Data in R2F . (b) Data in RKHS Fkr . ˜ Figure 1: (a) ORK under sampling imbalance. (b) Data in RKHS induced by ORK. 3 Multi-Body Motion Segmentation using ORK In this section, we describe how ORK is used for multi-body motion segmentation. 3.1 Outlier rejection via non-linear dimensionality reduction Denote by Fkr the Reproducing Kernel Hilbert Space (RKHS) induced by kr . Let matrix A = ˜ ˜ [φ(x1 ) . . . φ(xN )] contain the input data after it is mapped to Fkr . The kernel matrix K = AT A is ˜ computed using the kernel function kr as ˜ Kp,q = φ(xp ), φ(xq ) = kr (xp , xq ), p, q ∈ {1 . . . N }. ˜ (8) Since kr is a valid Mercer kernel, K is guaranteed to be positive semi-definite [12]. Let K = ˜ Q∆QT be the eigenvalue decomposition (EVD) of K. Then the rank-n Kernel Singular Value Decomposition (Kernel SVD) [12] of A is 1 1 An = [AQn (∆n )− 2 ][(∆n ) 2 ][(Qn )T ] ≡ Un Σn (Vn )T . n n (9) n Via the Matlab notation, Q = Q:,1:n and ∆ = ∆1:n,1:n . The left singular vectors U is an orthonormal basis for the n-dimensional principal subspace of the whole dataset in Fkr . Projecting ˜ the data onto the principal subspace yields 1 1 B = [AQn (∆n )− 2 ]T A = (∆n ) 2 (Qn )T , (10) n×N where B = [b1 . . . bN ] ∈ R is the reduced dimension version of A. Directions of the principal subspace are dominated by inlier points, since kr evaluates to a high value generally for them, but ˜ always to a low value for gross outliers. Moreover the kernel ensures that points from the same subspace are mapped to the same cluster and vice versa. Fig. 1(b) illustrates this condition. Fig. 2(a)(left) shows the first frame of sequence “Cars10” from the Hopkins 155 dataset [18] with 100 false trajectories of Brownian motion added to the original data (297 points). The corresponing RKHS norm histogram for n = 3 is displayed in Fig. 2(b). The existence of two distinct modes, 4 15 Outlier mode Bin count Inlier mode 10 5 0 (a) (left) Before and (right) after outlier removal. Blue dots are inliers while red dots are added outliers. 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 Vector norm in principal subspace 0.18 0.2 (b) Actual norm histogram of “cars10”. Figure 2: Demonstration of outlier rejection on sequence “cars10” from Hopkins 155. corresponding respectively to inliers and outliers, is evident. We exploit this observation for outlier rejection by discarding data with low norms in the principal subspace. The cut-off threshold ψ can be determined by analyzing the shape of the distribution. For instance we can fit a 1D Gaussian Mixture Model (GMM) with two components and set ψ as the point of equal Mahalanobis distance between the two components. However, our experimentation shows that an effective threshold can be obtained by simply setting ψ as the average value of all the norms, i.e. ψ= 1 N N bi . (11) i=1 This method was applied uniformly on all the sequences in our experiments in Sec. 4. Fig. 2(a)(right) shows an actual result of the method on Fig. 2(a)(left). 3.2 Recovering the number of motions and subspace clustering After outlier rejection, we further take advantage of the mapping induced by ORK for recovering the number of motions and subspace clustering. On the remaining data, we perform Kernel PCA [11] to seek the principal components which maximize the variance of the data in the RKHS, as Fig. 1(b) illustrates. Let {yi }i=1,...,N ′ be the N ′ -point subset of the input data that remains after outlier removal, where N ′ < N . Denote by C = [φ(y1 ) . . . φ(yN ′ )] the data matrix after mapping the data ˜ to Fkr , and by symbol C the result of adjusting C with the empirical mean of {φ(y1 ), . . . , φ(yN ′ )}. ˜ ˜ ˜ ˜ The centered kernel matrix K′ = CT C [11] can be obtained as 1 ˜ K′ = ν T K′ ν, ν = [IN ′ − ′ 1N ′ ,N ′ ], (12) N where K′ = CT C is the uncentered kernel matrix, Is and 1s,s are respectively the s × s identity ˜ ˜ matrix and a matrix of ones. If K′ = RΩRT is the EVD of K′ , then we obtain first-m kernel m ˜ principal components P of C as the first-m left singular vectors of C , i.e. 1 ˜ Pm = CRm (Ωm )− 2 , (13) where Rm = R:,1:m and Ω1:m,1:m ; see Eq. (9). Projecting the data on the principal components yields 1 D = [d1 . . . dN ′ ] = (Ωm ) 2 (Rm )T , (14) ′ where D ∈ Rm×N . The affine subspace span(Pm ) maximizes the spread of the centered data in the RKHS, and the projection D offers an effective representation for clustering. Fig. 3(a) shows the Kernel PCA projection results for m = 3 on the sequence in Fig. 2(a). The number of clusters in D is recovered via spectral clustering. More specifically we apply the Normalized Cut (Ncut) [13] algorithm. A fully connected graph is first derived from the data, where ′ ′ its weighted adjacency matrix W ∈ RN ×N is obtained as Wp,q = exp(− dp − dq 2 /2δ 2 ), (15) and δ is taken as the average nearest neighbour distance in the Euclidean sense among the vectors in D. The Laplacian matrix [13] is then derived from W and eigendecomposed. Under Ncut, 5 0.1 0.05 0 −0.05 −0.1 0.1 −0.15 0.15 0.08 0.1 0.05 0 −0.05 −0.1 0.06 (a) Kernel PCA and Ncut results. (b) W matrix. (c) Final result for “cars10”. Figure 3: Actual results on the motion sequence in Fig. 2(a)(left). the number of clusters is revealed as the number of eigenvalues of the Laplacian that are zero or numerically insignificant. With this knowledge, a subsequent k-means step is then performed to cluster the points. Fig. 3(b) shows W for the input data in Fig. 2(a)(left) after outlier removal. It can be seen that strong affinity exists between points from the same cluster, thus allowing accurate clustering. Figs. 3(a) and 3(c) illustrate the final clustering result for the data in Fig. 2(a)(left). There are several reasons why spectral clustering under our framework is more successful than previous methods. Firstly, we perform an effective outlier rejection step that removes bad trajectories that can potentially mislead the clustering. Secondly, the mapping induced by ORK deliberately separates the trajectories based on their cluster membership. Finally, we perform Kernel PCA to maximize the variance of the data. Effectively this also improves the separation of clusters, thus facilitating an accurate recovery of the number of clusters and also the subsequent segmentation. This distinguishes our work from previous clustering based methods [21, 5] which tend to operate without maximizing the between-class scatter. Results in Sec. 4 validate our claims. 4 Results Henceforth we indicate the proposed method as “ORK”. We leverage on a recently published benchmark on affine model motion segmentation [18] as a basis of comparison. The benchmark was evaluated on the Hopkins 155 dataset4 which contains 155 sequences with tracked point trajectories. A total of 120 sequences have two motions while 35 have three motions. The sequences contain degenerate and non-degenerate motions, independent and partially dependent motions, articulated motions, nonrigid motions etc. In terms of video content three categories exist: Checkerboard sequences, traffic sequences (moving cars, trucks) and articulated motions (moving faces, people). 4.1 Details on benchmarking Four major algorithms were compared in [18]: Generalized PCA (GPCA) [19], Local Subspace Affinity (LSA) [21], Multi-Stage Learning (MSL) [14] and RANSAC [17]. Here we extend the benchmark with newly reported results from Locally Linear Manifold Clustering (LLMC) [5] and Agglomerative Lossy Compression (ALC) [10, 9]. We also compare our method against Kanatani and Matsunaga’s [8] algorithm (henceforth, the “KM” method) in estimating the number of independent motions in the video sequences. Note that KM per se does not perform motion segmentation. For the sake of objective comparisons we use only implementations available publicly5. Following [18], motion segmentation performance is evaluated in terms of the labelling error of the point trajectories, where each point in a sequence has a ground truth label, i.e. number of mislabeled points . (16) classification error = total number of points Unlike [18], we also emphasize on the ability of the methods in recovering the number of motions. However, although the methods compared in [18] (except RANSAC) theoretically have the means to 4 Available at http://www.vision.jhu.edu/data/hopkins155/. For MSL and KM, see http://www.suri.cs.okayama-u.ac.jp/e-program-separate.html/. For GPCA, LSA and RANSAC, refer to the url for the Hopkins 155 dataset. 5 6 do so, their estimation of the number of motions is generally unrealiable and the benchmark results in [18] were obtained by revealing the actual number of motions to the algorithms. A similar initialization exists in [5, 10] where the results were obtained by giving LLMC and ALC this knowledge a priori (for LLMC, this was given at least to the variant LLMC 4m during dimensionality reduction [5], where m is the true number of motions). In the following subsections, where variants exist for the compared algorithms we use results from the best performing variant. In the following the number of random hypotheses M and step size h for ORK are fixed at 1000 and 300 respectively, and unlike the others, ORK is not given knowledge of the number of motions. 4.2 Data without gross outliers We apply ORK on the Hopkins 155 dataset. Since ORK uses random sampling we repeat it 100 times for each sequence and average the results. Table 1 depicts the obtained classification error among those from previously proposed methods. ORK (column 9) gives comparable results to the other methods for sequences with 2 motions (mean = 7.83%, median = 0.41%). For sequences with 3 motions, ORK (mean = 12.62%, median = 4.75%) outperforms GPCA and RANSAC, but is slightly less accurate than the others. However, bear in mind that unlike the other methods ORK is not given prior knowledge of the true number of motions and has to estimate this independently. Column Method 1 REF 2 GPCA Mean Median 2.03 0.00 4.59 0.38 Mean Median 5.08 2.40 28.66 28.26 3 4 5 6 LSA MSL RANSAC LLMC Sequences with 2 motions 3.45 4.14 5.56 3.62 0.59 0.00 1.18 0.00 Sequences with 3 motions 9.73 8.23 22.94 8.85 2.33 1.76 22.03 3.19 8 ALC 9 ORK 10 ORK∗ 3.03 0.00 7.83 0.41 1.27 0.00 6.26 1.02 12.62 4.75 2.09 0.05 Table 1: Classification error (%) on Hopkins 155 sequences. REF represents the reference/control method which operates based on knowledge of ground truth segmentation. Refer to [18] for details. We also separately investigate the accuracy of ORK in estimating the number of motions, and compare it against KM [8] which was proposed for this purpose. Note that such an experiment was not attempted in [18] since approaches compared therein generally do not perform reliably in estimating the number of motions. The results in Table 2 (columns 1–2) show that for sequences with two motions, KM (80.83%) outperforms ORK (67.37%) by ≈ 15 percentage points. However, for sequences with three motions, ORK (49.66%) vastly outperforms KM (14.29%) by more than doubling the percentage points of accuracy. The overall accuracy of KM (65.81%) is slightly better than ORK (63.37%), but this is mostly because sequences with two motions form the majority in the dataset (120 out of 155). This leads us to conclude that ORK is actually the superior method here. Dataset Column Method 2 motions 3 motions Overall Hopkins 155 1 2 KM ORK 80.83% 67.37% 14.29% 49.66% 65.81% 63.37% Hopkins 155 + Outliers 3 4 KM ORK 00.00% 47.58% 100.00% 50.00% 22.58% 48.13% Table 2: Accuracy in determining the number of motions in a sequence. Note that in the experiment with outliers (columns 3–4), KM returns a constant number of 3 motions for all sequences. We re-evaluate the performance of ORK by considering only results on sequences where the number of motions is estimated correctly by ORK (there are about 98 ≡ 63.37% of such cases). The results are tabulated under ORK∗ (column 10) in Table 1. It can be seen that when ORK estimates the number of motions correctly, it is significantly more accurate than the other methods. Finally, we compare the speed of the methods in Table 3. ORK was implemented and run in Matlab on a Dual Core Pentium 3.00GHz machine with 4GB of main memory (this is much less powerful 7 than the 8 Core Xeon 3.66GHz with 32GB memory used in [18] for the other methods in Table 3). The results show that ORK is comparable to LSA, much faster than MSL and ALC, but slower than GPCA and RANSAC. Timing results of LLMC are not available in the literature. Method 2 motions 3 motions GPCA 324ms 738ms LSA 7.584s 15.956s MSL 11h 4m 1d 23h RANSAC 175ms 258ms ALC 10m 32s 10m 32s ORK 4.249s 8.479s Table 3: Average computation time on Hopkins 155 sequences. 4.3 Data with gross outliers We next examine the ability of the proposed method in dealing with gross outliers in motion data. For each sequence in Hopkins 155, we add 100 gross outliers by creating trajectories corresponding to mistracks or spuriously occuring points. These are created by randomly initializing 100 locations in the first frame and allowing them to drift throughout the sequence according to Brownian motion. The corrupted sequences are then subjected to the algorithms for motion segmentation. Since only ORK is capable of rejecting outliers, the classification error of Eq. (16) is evaluated on the inlier points only. The results in Table 4 illustrate that ORK (column 4) is the most accurate method by a large margin. Despite being given the true number of motions a priori, GPCA, LSA and RANSAC are unable to provide satisfactory segmentation results. Column Method Mean Median Mean Median 1 2 3 4 GPCA LSA RANSAC ORK Sequences with 2 motions 28.66 24.25 30.64 16.50 30.96 26.51 32.36 10.54 Sequences with 3 motions 40.61 30.94 42.24 19.99 41.30 27.68 43.43 8.49 5 ORK∗ 1.62 0.00 2.68 0.09 Table 4: Classification error (%) on Hopkins 155 sequences with 100 gross outliers per sequence. In terms of estimating the number of motions, as shown in column 4 in Table 2 the overall accuracy of ORK is reduced to 48.13%. This is contributed mainly by the deterioration in accuracy on sequences with two motions (47.58%), although the accuracy on sequences with three motions are maintained (50.00%). This is not a surprising result, since sequences with three motions generally have more (inlying) point trajectories than sequences with two motions, thus the outlier rates for sequences with three motions are lower (recall that a fixed number of 100 false trajectories are added). On the other hand, the KM method (column 3) is completely overwhelmed by the outliers— for all the sequences with outliers it returned a constant “3” as the number of motions. We again re-evaluate ORK by considering results from sequences (now with gross outliers) where the number of motions is correctly estimated (there are about 75 ≡ 48.13% of such cases). The results tabulated under ORK∗ (column 5) in Table 4 show that the proposed method can accurately segment the point trajectories without being influenced by the gross outliers. 5 Conclusions In this paper we propose a novel and highly effective approach for multi-body motion segmentation. Our idea is based on encapsulating random hypotheses in a novel Mercel kernel and statistical learning. We evaluated our method on the Hopkins 155 dataset with results showing that the idea is superior other state-of-the-art approaches. It is by far the most accurate in terms of estimating the number of motions, and it excels in segmentation accuracy despite lacking prior knowledge of the number of motions. The proposed idea is also highly robust towards outliers in the input data. Acknowledgements. We are grateful to the authors of [18] especially Ren´ Vidal for discussions e and insights which have been immensely helpful. 8 References [1] T. Boult and L. Brown. Factorization-based segmentation of motions. In IEEE Workshop on Motion Understanding, 1991. [2] T.-J. Chin, H. Wang, and D. Suter. Robust fitting of multiple structures: The statistical learning approach. In ICCV, 2009. [3] J. Costeira and T. Kanade. A multibody factorization method for independently moving objects. IJCV, 29(3):159–179, 1998. [4] M. A. Fischler and R. C. Bolles. Random sample concensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. of the ACM, 24:381–395, 1981. [5] A. Goh and R. Vidal. Segmenting motions of different types by unsupervised manifold clustering. In CVPR, 2007. [6] A. Gruber and Y. Weiss. Multibody factorization with uncertainty and missing data using the EM algorithm. In CVPR, 2004. [7] K. Kanatani. Motion segmentation by subspace separation and model selection. In ICCV, 2001. [8] K. Kanatani and C. Matsunaga. Estimating the number of independent motions for multibody segmentation. In ACCV, 2002. [9] Y. Ma, H. Derksen, W. Hong, and J. Wright. Segmentation of multivariate mixed data via lossy coding and compression. TPAMI, 29(9):1546–1562, 2007. [10] S. Rao, R. Tron, Y. Ma, and R. Vidal. Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories. In CVPR, 2008. [11] B. Sch¨ lkopf, A. Smola, and K. R. M¨ ller. Nonlinear component analysis as a kernel eigeno u value problem. Neural Computation, 10:1299–1319, 1998. [12] J. Shawe-Taylor and N. Cristianini. Kernel methods for pattern analysis. Cambridge University Press, 2004. [13] J. Shi and J. Malik. Normalized cuts and image segmentation. TPAMI, 22(8):888–905, 2000. [14] Y. Sugaya and K. Kanatani. Geometric structure of degeneracy for multi-body motion segmentation. In Workshop on Statistical Methods in Video Processing, 2004. [15] R. Toldo and A. Fusiello. Robust multiple structures estimation with J-Linkage. In ECCV, 2008. [16] C. Tomasi and T. Kanade. Shape and motion from image streams under orthography. IJCV, 9(2):137–154, 1992. [17] P. Torr. Geometric motion segmentation and model selection. Phil. Trans. Royal Society of London, 356(1740):1321–1340, 1998. [18] R. Tron and R. Vidal. A benchmark for the comparison of 3-D motion segmentation algorithms. In CVPR, 2007. [19] R. Vidal and R. Hartley. Motion segmentation with missing data by PowerFactorization and Generalized PCA. In CVPR, 2004. [20] R. Vidal, Y. Ma, and S. Sastry. Generalized Principal Component Analysis (GPCA). TPAMI, 27(12):1–15, 2005. [21] J. Yan and M. Pollefeys. A general framework for motion segmentation: independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In ECCV, 2006. [22] L. Zelnik-Manor and M. Irani. Degeneracies, dependencies and their implications on multibody and multi-sequence factorization. In CVPR, 2003. [23] W. Zhang and J. Koseck´ . Nonparametric estimation of multiple structures with outliers. In a Dynamical Vision, ICCV 2005 and ECCV 2006 Workshops, 2006. 9
6 0.69430053 81 nips-2009-Ensemble Nystrom Method
7 0.68670666 223 nips-2009-Sparse Metric Learning via Smooth Optimization
8 0.68586564 257 nips-2009-White Functionals for Anomaly Detection in Dynamical Systems
9 0.68545002 67 nips-2009-Directed Regression
10 0.66915768 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization
11 0.66784745 36 nips-2009-Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing
12 0.66469556 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers
13 0.66205752 254 nips-2009-Variational Gaussian-process factor analysis for modeling spatio-temporal data
14 0.65707469 43 nips-2009-Bayesian estimation of orientation preference maps
15 0.65563488 177 nips-2009-On Learning Rotations
16 0.649616 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms
17 0.64774382 22 nips-2009-Accelerated Gradient Methods for Stochastic Optimization and Online Learning
18 0.64692897 163 nips-2009-Neurometric function analysis of population codes
19 0.64499342 55 nips-2009-Compressed Least-Squares Regression
20 0.64399534 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models