nips nips2013 nips2013-73 knowledge-graph by maker-knowledge-mining

73 nips-2013-Convex Relaxations for Permutation Problems

Source: pdf

Author: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre D'Aspremont

Abstract: Seriation seeks to reconstruct a linear order between variables using unsorted similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We prove the equivalence between the seriation and the combinatorial 2-SUM problem (a quadratic minimization problem over permutations) over a class of similarity matrices. The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we produce a convex relaxation for the 2-SUM problem to improve the robustness of solutions in a noisy setting. This relaxation also allows us to impose additional structural constraints on the solution, to solve semi-supervised seriation problems. We present numerical experiments on archeological data, Markov chains and gene sequences. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 It has direct applications in archeology and shotgun gene sequencing for example. [sent-23, score-0.317]

2 We prove the equivalence between the seriation and the combinatorial 2-SUM problem (a quadratic minimization problem over permutations) over a class of similarity matrices. [sent-24, score-0.782]

3 The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we produce a convex relaxation for the 2-SUM problem to improve the robustness of solutions in a noisy setting. [sent-25, score-0.934]

4 This relaxation also allows us to impose additional structural constraints on the solution, to solve semi-supervised seriation problems. [sent-26, score-0.725]

5 The seriation problem seeks to reconstruct this linear ordering based on unsorted, possibly noisy, similarity information. [sent-30, score-0.758]

6 envelope reduction algorithms for sparse linear algebra [2], in identifying interval graphs for scheduling [3], or in shotgun DNA sequencing where a single strand of genetic material is reconstructed from many cloned shorter reads, i. [sent-34, score-0.312]

7 With shotgun gene sequencing applications in mind, many references focused on the Consecutive Ones Problem (C1P) which seeks to permute the rows of a binary matrix so that all the ones in each column are contiguous. [sent-37, score-0.413]

8 In particular, [3] studied further connections to interval graphs and [6] crucially showed that a solution to C1P can be obtained by solving the seriation problem on the squared data matrix. [sent-38, score-0.651]

9 On the algorithmic front, the seriation problem was shown to be NP-Complete by [10]. [sent-40, score-0.581]

10 More general ordering problems were studied extensively in operations research, mostly in connection with the Quadratic Assignment Problem (QAP), for which several convex relaxations were studied in e. [sent-43, score-0.291]

11 Since a matrix is a permutation matrix if and only if it is both orthogonal and 1 doubly stochastic, much work also focused on producing semideﬁnite relaxations to orthogonality constraints [13, 14]. [sent-46, score-0.828]

12 These programs are convex hence tractable but the relaxations are usually very large and scale poorly. [sent-47, score-0.184]

13 More recently however, [15] produced a spectral algorithm that exactly solves the seriation problem in a noiseless setting, in results that are very similar to those obtained on the interlacing of eigenvectors for Sturm Liouville operators. [sent-48, score-0.807]

14 They show that for similarity matrices computed from serial variables (for which a total order exists), the ordering of the second eigenvector of the Laplacian (a. [sent-49, score-0.292]

15 Here, we show that the solution of the seriation problem explicitly minimizes a quadratic function. [sent-53, score-0.67]

16 While this quadratic problem was mentioned explicitly in [15], no connection was made between the combinatorial and spectral solutions. [sent-54, score-0.263]

17 Our result shows in particular that the 2-SUM minimization problem mentioned in [10], and deﬁned below, is polynomially solvable for matrices coming from serial data. [sent-55, score-0.177]

18 This result allows us to write seriation as a quadratic minimization problem over permutation matrices and we then produce convex relaxations for this last problem. [sent-56, score-1.204]

19 This relaxation appears to be more robust to noise than the spectral or combinatorial techniques in a number of examples. [sent-57, score-0.294]

20 Perhaps more importantly, it allows us to impose additional structural constraints to solve semi-supervised seriation problems. [sent-58, score-0.643]

21 We also develop a fast algorithm for projecting on the set of doubly stochastic matrices, which is of independent interest. [sent-59, score-0.285]

22 In Section 2, we show a decomposition result for similarity matrices formed from the C1P problem. [sent-61, score-0.178]

23 This decomposition allows to make the connection between the seriation and 2-SUM minimization problems on these matrices. [sent-62, score-0.616]

24 In Section 3 we use these results to write convex relaxations of the seriation problem by relaxing permutation matrices as doubly stochastic matrices in the 2-SUM minimization problem. [sent-63, score-1.545]

25 , n} while the notation ⇧ (in capital letter) will refer to the corresponding matrix permutation, which is a {0, 1} matrix suchP ⇧ij = 1 P ⇡(j) = i. [sent-74, score-0.156]

26 For a vector that iff n n 2 y 2 Rn , we write var(y) its variance, with var(y) = i=1 yi /n ( i=1 yi /n)2 , we also write y[u,v] 2 Rv u+1 the vector (yu , . [sent-75, score-0.215]

27 We write Sn the set of symmetric matrices of dimension n, k · kF denotes the Frobenius norm and i (X) the ith eigenvalue (in increasing order) of X. [sent-80, score-0.225]

28 2 Seriation & consecutive ones Given a symmetric, binary matrix A, we will focus on variations of the following 2-SUM combinatorial minimization problem, studied in e. [sent-81, score-0.271]

29 This problem is used for example to reduce the envelope of sparse matrices and is shown in [10, Th. [sent-84, score-0.154]

30 When A has a speciﬁc structure, [15] show that a related matrix reordering problem used for seriation can be solved explicitly by a spectral algorithm. [sent-87, score-0.887]

31 However, the results in [15] do not explicitly link spectral ordering and the optimum of (1). [sent-88, score-0.247]

32 For some instances of A related to seriation and consecutive one problems, we show below that the spectral ordering directly minimizes the objective of problem (1). [sent-89, score-0.883]

33 1 Binary matrices Let A 2 Sn and y 2 Rn , we focus on a generalization of the 2-SUM minimization problem Pn minimize f (y⇡ ) , i,j=1 Aij (y⇡(i) y⇡(j) )2 subject to ⇡ 2 P. [sent-92, score-0.208]

34 (2) The main point of this section is to show that if A is the permutation of a similarity matrix formed from serial data, then minimizing (2) recovers the correct variable ordering. [sent-93, score-0.378]

35 1 We say that the matrix A 2 Sn is an R-matrix (or Robinson matrix) iff it is symmetric and satisﬁes Ai,j  Ai,j+1 and Ai+1,j  Ai,j in the lower triangle, where 1  j < i  n. [sent-96, score-0.168]

36 8) which is an R-matrix (center), and a matrix a aT where a is a unimodal vector (right). [sent-105, score-0.162]

37 pre-P) iff there is a permutation ⇧ such that ⇧A⇧T is an R-matrix (resp. [sent-109, score-0.247]

38 We can write ij Aij (yi yj )2 = y T LA y where LA = diag(A1) A is the Laplacian of matrix A, which is a block matrix equal to (v u + 1) {i=j} 1 for u  i, j  v. [sent-122, score-0.208]

39 If ⇧ is such that ⇧C⇧T (hence ⇧A⇧T ) is an R-matrix, then the corresponding permutation ⇡ solves the combinatorial minimization problem (2) for A = C 2 . [sent-134, score-0.347]

40 5 show that each CUT term is minimized by a monotonic sequence, but yi = ai+b means here that all monotonic subsets of y of a given length have the same (minimal) variance, attained by ⇧y. [sent-140, score-0.161]

41 We now show that minimizing (2) also recovers the correct ordering for these more general matrix classes. [sent-146, score-0.185]

42 We call a matrix A pre-Q iff there is a permutation ⇧ such that ⇧A is a Q-matrix. [sent-152, score-0.325]

43 Remark that when A, B are {0, 1} matrices and w = 1, min{Aik , Bkj } = Aik Bkj , so the circle product matches the regular matrix product AB T . [sent-159, score-0.185]

44 Let A = C C T , if ⇧ is such that ⇧A⇧T is an R-matrix, then the corresponding permutation ⇡ solves the combinatorial minimization problem (2). [sent-177, score-0.347]

45 10 show that there is a permutation ⇧ such that ⇧(C C T )⇧T is a sum of CUT matrices (hence a R-matrix). [sent-181, score-0.301]

46 This result shows that if A is pre-R and can be written A = C C T with C pre-Q, then the permutation that makes A an R-matrix also solves (2). [sent-186, score-0.273]

47 3 Convex relaxations for permutation problems In the sections that follow, we will use the combinatorial results derived above to produce convex relaxations of optimization problems written over the set of permutation matrices. [sent-190, score-0.797]

48 We ﬁrst recall the main result from [15] which shows how to reorder pre-R matrices in a noise free setting. [sent-193, score-0.172]

49 The results in [15] provide a polynomial time solution to the R-matrix ordering problem in a noiseless setting. [sent-199, score-0.185]

50 The results in the previous section made the connection between the spectral ordering in [15] and problem (2). [sent-201, score-0.247]

51 In what follows, we will use (2) to produce convex relaxations to matrix ordering problems in a noisy setting. [sent-202, score-0.369]

52 Numerical experiments in Section 4 show that semi-supervised seriation solutions are sometimes signiﬁcantly more robust to noise than the spectral solutions ordered from the Fiedler vector. [sent-204, score-0.772]

53 We write Dn the set of doubly stochastic matrices in Rn⇥n , i. [sent-206, score-0.444]

54 Classical results show that the set of doubly stochastic matrices is the convex hull of the set of permutation matrices. [sent-210, score-0.65]

55 a matrix is a permutation matrix if and only if it is both doubly stochastic and orthogonal. [sent-213, score-0.635]

56 This means that we can directly write a convex relaxation to the combinatorial problem (2) by replacing P with its convex hull Dn , to get minimize g T ⇧T LA ⇧g subject to ⇧ 2 Dn , (3) where g = (1, . [sent-214, score-0.4]

57 To provide a solution to the combinatorial problem (2), we then generate permutations from the doubly stochastic optimal solution to (3) (we will describe an efﬁcient procedure to do so in §3). [sent-221, score-0.509]

58 The results of Section 2 show that the optimal solution to (2) also solves the seriation problem in the noiseless setting when the matrix A is of the form C C T with C a Q-matrix and y is an afﬁne transform of the vector (1, . [sent-222, score-0.783]

59 As the set of permutation matrices P is the intersection of the set of doubly stochastic matrices D and the set of orthogonal matrices O, i. [sent-233, score-0.833]

60 p As a doubly stochastic matrix of Frobenius norm n is necessarily orthogonal, we would ideally like to solve 1 minimize p Tr(Y T ⇧T LA ⇧Y ) µ k⇧k2 F p (5) subject to eT ⇧g + 1  eT ⇧g, ⇧1 = 1, ⇧T 1 = 1, ⇧ 0, n 1 with µ large enough to guarantee that the global solution is indeed a permutation. [sent-236, score-0.467]

61 The QP relaxation allows us to add convex structural constraints in the problem. [sent-245, score-0.208]

62 In gene sequencing applications, one may want to constrain the distance between two elements (e. [sent-249, score-0.206]

63 mate reads), which would read a  ⇡(i) ⇡(j)  b and introduce an afﬁne inequality on the variable ⇧ in the QP relaxation of the form a  eT ⇧g eT ⇧g  b. [sent-251, score-0.192]

64 More generally, we can rewrite problem (6) with nc additional linear constraints as follows 1 minimize p Tr(Y T ⇧T LA ⇧Y ) µ kP ⇧k2 F p (7) subject to DT ⇧g +  0, ⇧1 = 1, ⇧T 1 = 1, ⇧ 0, where D is a matrix of size n ⇥ nc and is a vector of size nc . [sent-253, score-0.264]

65 This procedure is based on the fact that a permutation can be deﬁned from a doubly stochastic matrix D by the order induced on a monotonic vector. [sent-256, score-0.623]

66 To each v, we can associate a permutation ⇧ such that ⇧Dv is monotonically increasing. [sent-258, score-0.194]

67 If D is a permutation matrix, then the permutation ⇧ generated by this procedure will be constant, if D is a doubly stochastic matrix but not a permutation, it might ﬂuctuate. [sent-259, score-0.751]

68 Starting from a solution D to problem (6), we can use this procedure to generate many permutation matrices ⇧ and we pick the one with lowest cost y T ⇧T LA ⇧y in the combinatorial problem (2). [sent-260, score-0.411]

69 a matrix is a permutation matrix if and only if it is both doubly stochastic and orthogonal. [sent-265, score-0.635]

70 Semideﬁnite relaxations to orthogonality constraints have been developed in e. [sent-267, score-0.2]

71 The convex relaxation in (7) is a quadratic program in the variable ⇧ 2 Rn⇥n , which has dimension n2 . [sent-272, score-0.197]

72 Furthermore, most pre-R matrices formed by squaring pre-Q matrices are very sparse, which considerably speeds up linear algebra. [sent-274, score-0.282]

73 Solving (7) using the conditional gradient algorithm in [18] requires minimizing an afﬁne function over the set of doubly stochastic matrices at each iteration. [sent-280, score-0.392]

74 On the other hand, solving (7) using accelerated gradient algorithms requires solving a projection step on doubly stochastic matrices at each iteration [20]. [sent-282, score-0.456]

75 Given some matrix ⇧0 , the projection problem is written minimize 1 k⇧ ⇧0 k2 F 2 subject to DT ⇧g +  0, ⇧1 = 1, ⇧T 1 = 1, ⇧ 6 0 (8) in the variable ⇧ 2 Rn⇥n , with parameter g 2 Rn . [sent-284, score-0.177]

76 We reorder the rows of the Hodson’s Munsingen dataset (as provided by [22] and manually ordered by [6]), to date 59 graves from 70 recovered artifact types (graves from similar periods containing similar artifacts). [sent-292, score-0.151]

77 Note that the semi-supervised solution actually improves on both Kendall’s manual solution and on the spectral ordering. [sent-324, score-0.216]

78 The mutual information matrix of these variables must be decreasing with |i j| when ordered according to the true generating Markov chain [23, Th. [sent-327, score-0.158]

79 We can thus recover the order of the Markov chain by solving the seriation problem on this matrix. [sent-331, score-0.642]

80 In next generation shotgun gene sequencing experiments, genes are cloned about ten to a hundred times before being decomposed into very small subsequences called “reads”, each ﬁfty to a few hundreds base pairs long. [sent-336, score-0.347]

81 We generate artiﬁcial sequencing data by (uniformly) sampling reads from chromosome 22 of the human genome from NCBI, then store k-mer hit versus read in a binary matrix (a k-mer is a ﬁxed sequence of k base pairs). [sent-338, score-0.526]

82 If the reads are ordered correctly, this matrix should be C1P, hence we solve the C1P problem on the {0, 1}-matrix whose rows correspond to k-mers hits for each read, i. [sent-339, score-0.314]

83 the element (i, j) of the matrix is equal to one if k-mer j is included in read i. [sent-341, score-0.155]

84 02 Table 2: Kendall’s ⌧ between the true Markov chain ordering, the Fiedler vector, the seriation QP in (6) and the semi-supervised seriation QP in (7) with varying numbers of pairwise orders speciﬁed. [sent-381, score-1.191]

85 We observe the (randomly ordered) model covariance matrix (no noise), the sample covariance matrix with enough samples so the error is smaller than half of the spectral gap, then a sample covariance computed using much fewer samples so the spectral perturbation condition fails. [sent-382, score-0.436]

86 In practice, besides sequencing errors (handled relatively well by the high coverage of the reads), there are often repeats in long genomes. [sent-385, score-0.157]

87 reads that are known to be separated by a given number of base pairs in the original genome. [sent-389, score-0.215]

88 While our algorithm for solving (7) only scales up to a few thousands base pairs on a regular desktop, it can be used to solve the sequencing problem hierarchically, i. [sent-391, score-0.185]

89 Graph connectivity issues can be solved directly using spectral information. [sent-394, score-0.167]

90 Figure 2: We plot the reads ⇥ reads matrix measuring the number of common k-mers between read pairs, reordered according to the spectral ordering on two regions (two plots on the left), then the Fiedler and Fiedler+QP read orderings versus true ordering (two plots on the right). [sent-395, score-1.016]

91 In Figure 2, the two ﬁrst plots show the result of spectral ordering on simulated reads from human chromosome 22. [sent-397, score-0.465]

92 The full R matrix formed by squaring the reads ⇥ kmers matrix is too large to be plotted in MATLAB and we zoom in on two diagonal block submatrices. [sent-398, score-0.409]

93 In the ﬁrst one, the reordering is good and the matrix has very low bandwidth, the corresponding gene segment (or contig. [sent-399, score-0.222]

94 In the second the reordering is less reliable, and the bandwidth is larger, the reconstructed gene segment contains errors. [sent-401, score-0.175]

95 The last two plots show recovered read position versus true read position for the Fiedler vector and the Fiedler vector followed by semisupervised seriation, where the QP relaxation is applied to the reads assembled by the spectral solution, on 250 000 reads generated in our experiments. [sent-402, score-0.746]

96 We see that the number of misplaced reads signiﬁcantly decreases in the semi-supervised seriation solution. [sent-403, score-0.806]

97 A spectral algorithm for envelope reduction of sparse matrices. [sent-413, score-0.187]

98 An analysis of spectral envelope reduction via quadratic assignment problems. [sent-442, score-0.272]

99 Sums of random symmetric matrices and quadratic optimization under orthogonality constraints. [sent-452, score-0.245]

100 A spectral algorithm for seriation and the consecutive ones problem. [sent-463, score-0.807]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('seriation', 0.581), ('fiedler', 0.341), ('doubly', 0.245), ('qp', 0.207), ('permutation', 0.194), ('reads', 0.185), ('spectral', 0.14), ('la', 0.14), ('sequencing', 0.123), ('relaxations', 0.12), ('ordering', 0.107), ('matrices', 0.107), ('cut', 0.097), ('unimodal', 0.084), ('gene', 0.083), ('relaxation', 0.082), ('rn', 0.08), ('matrix', 0.078), ('read', 0.077), ('permutations', 0.076), ('combinatorial', 0.072), ('shotgun', 0.071), ('kendall', 0.067), ('monotonic', 0.066), ('reorder', 0.065), ('convex', 0.064), ('reordering', 0.061), ('reg', 0.061), ('archeological', 0.06), ('bkj', 0.06), ('fogel', 0.06), ('reordered', 0.06), ('semide', 0.06), ('cu', 0.059), ('consecutive', 0.055), ('ecole', 0.054), ('iff', 0.053), ('write', 0.052), ('aij', 0.052), ('quadratic', 0.051), ('ordered', 0.051), ('orthogonality', 0.05), ('aik', 0.049), ('laplacian', 0.048), ('envelope', 0.047), ('solves', 0.046), ('dn', 0.045), ('sn', 0.045), ('circular', 0.044), ('similarity', 0.043), ('subject', 0.04), ('stochastic', 0.04), ('archeology', 0.04), ('cloned', 0.04), ('dzg', 0.04), ('misplaced', 0.04), ('mosek', 0.04), ('palaiseau', 0.04), ('squaring', 0.04), ('unsorted', 0.04), ('noiseless', 0.04), ('solution', 0.038), ('symmetric', 0.037), ('graves', 0.035), ('normale', 0.035), ('rieure', 0.035), ('sierra', 0.035), ('serial', 0.035), ('jenatton', 0.035), ('minimization', 0.035), ('repeats', 0.034), ('assignment', 0.034), ('orthogonal', 0.033), ('written', 0.033), ('chromosome', 0.033), ('mate', 0.033), ('solving', 0.032), ('structural', 0.032), ('ones', 0.031), ('paris', 0.031), ('reconstructed', 0.031), ('polytechnique', 0.031), ('tr', 0.03), ('constraints', 0.03), ('base', 0.03), ('nc', 0.03), ('spearman', 0.029), ('yi', 0.029), ('perturbations', 0.029), ('eigenvalue', 0.029), ('chain', 0.029), ('formed', 0.028), ('solved', 0.027), ('seeks', 0.027), ('var', 0.026), ('zi', 0.026), ('minimize', 0.026), ('permuted', 0.026), ('pn', 0.026), ('dna', 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 73 nips-2013-Convex Relaxations for Permutation Problems

Author: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre D'Aspremont

2 0.14163652 300 nips-2013-Solving the multi-way matching problem by permutation synchronization

Author: Deepti Pachauri, Risi Kondor, Vikas Singh

Abstract: The problem of matching not just two, but m different sets of objects to each other arises in many contexts, including ﬁnding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, Permutation Synchronization, which ﬁnds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efﬁcient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods. 1

3 0.11418654 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

Author: Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Muse, Guillermo Sapiro

Abstract: Graph matching is a challenging problem with very important applications in a wide range of ﬁelds, from image and video analysis to biological and biomedical problems. We propose a robust graph matching algorithm inspired in sparsityrelated techniques. We cast the problem, resembling group or collaborative sparsity formulations, as a non-smooth convex optimization problem that can be efﬁciently solved using augmented Lagrangian techniques. The method can deal with weighted or unweighted graphs, as well as multimodal data, where different graphs represent different types of data. The proposed approach is also naturally integrated with collaborative graph inference techniques, solving general network inference problems where the observed variables, possibly coming from different modalities, are not in correspondence. The algorithm is tested and compared with state-of-the-art graph matching techniques in both synthetic and real graphs. We also present results on multimodal graphs and applications to collaborative inference of brain connectivity from alignment-free functional magnetic resonance imaging (fMRI) data. The code is publicly available. 1

4 0.10406408 306 nips-2013-Speeding up Permutation Testing in Neuroimaging

Author: Chris Hinrichs, Vamsi Ithapu, Qinyuan Sun, Sterling C. Johnson, Vikas Singh

Abstract: Multiple hypothesis testing is a signiﬁcant problem in nearly all neuroimaging studies. In order to correct for this phenomena, we require a reliable estimate of the Family-Wise Error Rate (FWER). The well known Bonferroni correction method, while simple to implement, is quite conservative, and can substantially under-power a study because it ignores dependencies between test statistics. Permutation testing, on the other hand, is an exact, non-parametric method of estimating the FWER for a given α-threshold, but for acceptably low thresholds the computational burden can be prohibitive. In this paper, we show that permutation testing in fact amounts to populating the columns of a very large matrix P. By analyzing the spectrum of this matrix, under certain conditions, we see that P has a low-rank plus a low-variance residual decomposition which makes it suitable for highly sub–sampled — on the order of 0.5% — matrix completion methods. Based on this observation, we propose a novel permutation testing methodology which offers a large speedup, without sacriﬁcing the ﬁdelity of the estimated FWER. Our evaluations on four different neuroimaging datasets show that a computational speedup factor of roughly 50× can be achieved while recovering the FWER distribution up to very high accuracy. Further, we show that the estimated α-threshold is also recovered faithfully, and is stable. 1

5 0.086490028 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

Author: Dimitris Achlioptas, Zohar S. Karnin, Edo Liberty

Abstract: We consider the problem of selecting non-zero entries of a matrix A in order to produce a sparse sketch of it, B, that minimizes A B 2 . For large m n matrices, such that n m (for example, representing n observations over m attributes) we give sampling distributions that exhibit four important properties. First, they have closed forms computable from minimal information regarding A. Second, they allow sketching of matrices whose non-zeros are presented to the algorithm in arbitrary order as a stream, with O 1 computation per non-zero. Third, the resulting sketch matrices are not only sparse, but their non-zero entries are highly compressible. Lastly, and most importantly, under mild assumptions, our distributions are provably competitive with the optimal ofﬂine distribution. Note that the probabilities in the optimal ofﬂine distribution may be complex functions of all the entries in the matrix. Therefore, regardless of computational complexity, the optimal distribution might be impossible to compute in the streaming model. 1

6 0.076664507 116 nips-2013-Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA

7 0.074506097 75 nips-2013-Convex Two-Layer Modeling

8 0.068069458 155 nips-2013-Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition

9 0.066088676 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

10 0.064197846 108 nips-2013-Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion

11 0.06200891 91 nips-2013-Dirty Statistical Models

12 0.057897851 185 nips-2013-Matrix Completion From any Given Set of Observations

13 0.057875223 224 nips-2013-On the Sample Complexity of Subspace Learning

14 0.057581637 11 nips-2013-A New Convex Relaxation for Tensor Completion

15 0.057275463 222 nips-2013-On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization

16 0.056704931 202 nips-2013-Multiclass Total Variation Clustering

17 0.055682149 132 nips-2013-Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation

18 0.054965023 169 nips-2013-Learning to Prune in Metric and Non-Metric Spaces

19 0.054032125 33 nips-2013-An Approximate, Efficient LP Solver for LP Rounding

20 0.053829517 192 nips-2013-Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.15), (1, 0.064), (2, 0.065), (3, 0.074), (4, 0.004), (5, 0.033), (6, -0.043), (7, -0.033), (8, -0.039), (9, 0.002), (10, 0.021), (11, 0.017), (12, 0.084), (13, -0.01), (14, -0.026), (15, 0.019), (16, -0.05), (17, -0.002), (18, -0.076), (19, 0.031), (20, -0.021), (21, -0.083), (22, -0.019), (23, 0.004), (24, 0.004), (25, -0.092), (26, -0.017), (27, -0.015), (28, -0.083), (29, 0.06), (30, -0.025), (31, 0.026), (32, -0.004), (33, 0.079), (34, 0.037), (35, 0.065), (36, -0.026), (37, -0.073), (38, 0.031), (39, 0.153), (40, 0.056), (41, -0.004), (42, 0.066), (43, 0.066), (44, -0.048), (45, 0.114), (46, -0.09), (47, -0.066), (48, -0.041), (49, -0.01)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.90446955 73 nips-2013-Convex Relaxations for Permutation Problems

Author: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre D'Aspremont

2 0.75309193 300 nips-2013-Solving the multi-way matching problem by permutation synchronization

Author: Deepti Pachauri, Risi Kondor, Vikas Singh

3 0.69603664 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

Author: Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Muse, Guillermo Sapiro

4 0.65064228 306 nips-2013-Speeding up Permutation Testing in Neuroimaging

Author: Chris Hinrichs, Vamsi Ithapu, Qinyuan Sun, Sterling C. Johnson, Vikas Singh

5 0.62955308 328 nips-2013-The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited

Author: Matthias Hein, Simon Setzer, Leonardo Jost, Syama Sundar Rangapuram

Abstract: Hypergraphs allow one to encode higher-order relationships in data and are thus a very ﬂexible modeling tool. Current learning methods are either based on approximations of the hypergraphs via graphs or on tensor methods which are only applicable under special conditions. In this paper, we present a new learning framework on hypergraphs which fully uses the hypergraph structure. The key element is a family of regularization functionals based on the total variation on hypergraphs. 1

6 0.59896541 186 nips-2013-Matrix factorization with binary components

7 0.59119982 146 nips-2013-Large Scale Distributed Sparse Precision Estimation

8 0.58514643 302 nips-2013-Sparse Inverse Covariance Estimation with Calibration

9 0.58290219 45 nips-2013-BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables

10 0.57423824 35 nips-2013-Analyzing the Harmonic Structure in Graph-Based Learning

11 0.55684382 342 nips-2013-Unsupervised Spectral Learning of Finite State Transducers

12 0.55208266 350 nips-2013-Wavelets on Graphs via Deep Learning

13 0.54430145 202 nips-2013-Multiclass Total Variation Clustering

14 0.54222721 214 nips-2013-On Algorithms for Sparse Multi-factor NMF

15 0.53933549 117 nips-2013-Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis

16 0.53672183 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic

17 0.5224148 116 nips-2013-Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA

18 0.50890005 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

19 0.49475107 307 nips-2013-Speedup Matrix Completion with Side Information: Application to Multi-Label Learning

20 0.47510043 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.039), (33, 0.146), (34, 0.119), (35, 0.228), (41, 0.023), (49, 0.027), (56, 0.101), (70, 0.053), (85, 0.058), (89, 0.036), (93, 0.045), (95, 0.034)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.80625921 73 nips-2013-Convex Relaxations for Permutation Problems

Author: Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre D'Aspremont

2 0.79159433 321 nips-2013-Supervised Sparse Analysis and Synthesis Operators

Author: Pablo Sprechmann, Roee Litman, Tal Ben Yakar, Alexander M. Bronstein, Guillermo Sapiro

Abstract: In this paper, we propose a new computationally efﬁcient framework for learning sparse models. We formulate a uniﬁed approach that contains as particular cases models promoting sparse synthesis and analysis type of priors, and mixtures thereof. The supervised training of the proposed model is formulated as a bilevel optimization problem, in which the operators are optimized to achieve the best possible performance on a speciﬁc task, e.g., reconstruction or classiﬁcation. By restricting the operators to be shift invariant, our approach can be thought as a way of learning sparsity-promoting convolutional operators. Leveraging recent ideas on fast trainable regressors designed to approximate exact sparse codes, we propose a way of constructing feed-forward networks capable of approximating the learned models at a fraction of the computational cost of exact solvers. In the shift-invariant case, this leads to a principled way of constructing a form of taskspeciﬁc convolutional networks. We illustrate the proposed models on several experiments in music analysis and image processing applications. 1

3 0.70526838 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

Author: Yuhong Guo

Abstract: Principal component analysis (PCA), a well-established technique for data analysis and processing, provides a convenient form of dimensionality reduction that is effective for cleaning small Gaussian noises presented in the data. However, the applicability of standard principal component analysis in real scenarios is limited by its sensitivity to large errors. In this paper, we tackle the challenge problem of recovering data corrupted with errors of high magnitude by developing a novel robust transfer principal component analysis method. Our method is based on the assumption that useful information for the recovery of a corrupted data matrix can be gained from an uncorrupted related data matrix. Speciﬁcally, we formulate the data recovery problem as a joint robust principal component analysis problem on the two data matrices, with common principal components shared across matrices and individual principal components speciﬁc to each data matrix. The formulated optimization problem is a minimization problem over a convex objective function but with non-convex rank constraints. We develop an efﬁcient proximal projected gradient descent algorithm to solve the proposed optimization problem with convergence guarantees. Our empirical results over image denoising tasks show the proposed method can effectively recover images with random large errors, and signiﬁcantly outperform both standard PCA and robust PCA with rank constraints. 1

4 0.70435822 45 nips-2013-BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables

Author: Cho-Jui Hsieh, Matyas A. Sustik, Inderjit Dhillon, Pradeep Ravikumar, Russell Poldrack

Abstract: The 1 -regularized Gaussian maximum likelihood estimator (MLE) has been shown to have strong statistical guarantees in recovering a sparse inverse covariance matrix even under high-dimensional settings. However, it requires solving a difﬁcult non-smooth log-determinant program with number of parameters scaling quadratically with the number of Gaussian variables. State-of-the-art methods thus do not scale to problems with more than 20, 000 variables. In this paper, we develop an algorithm B IG QUIC, which can solve 1 million dimensional 1 regularized Gaussian MLE problems (which would thus have 1000 billion parameters) using a single machine, with bounded memory. In order to do so, we carefully exploit the underlying structure of the problem. Our innovations include a novel block-coordinate descent method with the blocks chosen via a clustering scheme to minimize repeated computations; and allowing for inexact computation of speciﬁc components. In spite of these modiﬁcations, we are able to theoretically analyze our procedure and show that B IG QUIC can achieve super-linear or even quadratic convergence rates. 1

5 0.70380741 97 nips-2013-Distributed Submodular Maximization: Identifying Representative Elements in Massive Data

Author: Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, Andreas Krause

Abstract: Many large-scale machine learning problems (such as clustering, non-parametric learning, kernel machines, etc.) require selecting, out of a massive data set, a manageable yet representative subset. Such problems can often be reduced to maximizing a submodular set function subject to cardinality constraints. Classical approaches require centralized access to the full data set; but for truly large-scale problems, rendering the data centrally is often impractical. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol G REE D I, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show, that under certain natural conditions, performance close to the (impractical) centralized approach can be achieved. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar-based clustering, on tens of millions of data points using Hadoop. 1

6 0.70312792 350 nips-2013-Wavelets on Graphs via Deep Learning

7 0.70300591 173 nips-2013-Least Informative Dimensions

8 0.70141745 201 nips-2013-Multi-Task Bayesian Optimization

9 0.70091617 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

10 0.70090646 49 nips-2013-Bayesian Inference and Online Experimental Design for Mapping Neural Microcircuits

11 0.70079708 5 nips-2013-A Deep Architecture for Matching Short Texts

12 0.69976473 333 nips-2013-Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

13 0.69876522 114 nips-2013-Extracting regions of interest from biological images with convolutional sparse block coding

14 0.6980691 186 nips-2013-Matrix factorization with binary components

15 0.69712764 161 nips-2013-Learning Stochastic Inverses

16 0.69666606 150 nips-2013-Learning Adaptive Value of Information for Structured Prediction

17 0.69655055 294 nips-2013-Similarity Component Analysis

18 0.69641048 251 nips-2013-Predicting Parameters in Deep Learning

19 0.6961726 22 nips-2013-Action is in the Eye of the Beholder: Eye-gaze Driven Model for Spatio-Temporal Action Localization

20 0.6961661 304 nips-2013-Sparse nonnegative deconvolution for compressive calcium imaging: algorithms and phase transitions