nips nips2013 nips2013-295 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma
Abstract: In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efficiency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efficient and effective than previous work. The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms “RASL” and “TILT” can be viewed as two special cases of our work, and yet each only performs part of the function of our method.
Reference: text
sentIndex sentText sentNum sentScore
1 com Abstract In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. [sent-6, score-0.149]
2 Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. [sent-7, score-1.014]
3 To improve the computational efficiency, we introduce a proximal gradient step to the alternating direction minimization method. [sent-8, score-0.151]
4 The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. [sent-11, score-0.219]
5 Many revolutionary new tools have been developed that enable people to recover low-dimensional structures in the form of sparse vectors or low-rank matrices in high dimensional data. [sent-15, score-0.134]
6 In the literature, it has been shown that for matrix data, if the data is a deformed or corrupted version of an intrinsically low-rank matrix, one can recover the rectified low-rank structure despite different types of deformation (linear or nonlinear) and severe corruptions. [sent-19, score-0.214]
7 Such concepts and methods have been successfully applied to rectify the so-called low-rank textures [1] and to align multiple correlated images (such as video frames or human faces) [2, 3, 4, 5, 6]. [sent-20, score-0.244]
8 However, when applied to the data of higher-order tensorial form, such as videos or 3D range data, these tools are only able to harness one type of low-dimensional structure at a time, and are not able to exploit the low-dimensional 1 tensorial structures in the data. [sent-21, score-0.372]
9 For instance, the previous work of TILT rectifies a low-rank textural region in a single image [1] while RASL aligns multiple correlated images [6]. [sent-22, score-0.111]
10 A natural question arises: can we simultaneously harness all such low-dimensional structures in an image sequence by viewing it as a three-order tensor? [sent-24, score-0.15]
11 Actually, many existing visual data can be naturally viewed as three-order (or even higher-order) tensors (e. [sent-25, score-0.214]
12 For tensorial data, however, one major challenge lies in an appropriate definition of the rank of a tensor, which corresponds to the notion of intrinsic “dimension” or “degree of freedom” for the tensorial data. [sent-30, score-0.382]
13 Traditionally, there are two definitions of tensor rank, which are based on PARAFAC decomposition [7] and Tucker decomposition [8] respectively. [sent-31, score-0.586]
14 Similar to the definition of matrix rank, the rank of a tensor based on PARAFAC decomposition is defined as the minimum number of rank-one decompositions of a given tensor. [sent-32, score-0.725]
15 However, this definition rank is a nonconvex and nonsmooth function on the tensor space, and direct minimization of this function is an NP-hard problem. [sent-33, score-0.681]
16 An alternative definition of tensor rank is based on the so-called Tucker decomposition, which results in a vector of the ranks of a set of matrices unfolded from the tensor. [sent-34, score-0.761]
17 Due to the recent breakthroughs in the recovery of low-rank matrices [9], the latter definition has received increasing attention. [sent-35, score-0.14]
18 [10] adopt the sum of the ranks of the different unfolding matrices as the rank of the tensor data, which is in turn approximated by the sum of their nuclear norms. [sent-37, score-1.06]
19 They then apply the alternating direction method (ADM) to solve the tensor completion problem with Gaussian observation noise. [sent-38, score-0.583]
20 Instead of directly adding up the ranks of the unfolding matrices, a weighted sum of the ranks of the unfolding matrices is introduced by Liu et al. [sent-39, score-0.64]
21 [12] and they also proposed several optimization algorithms to estimate missing values for tensorial visual data (such as color images). [sent-40, score-0.183]
22 In [13], three different strategies have been developed to extend the trace-norm regularization to tensors: (1) tensors treated as matrices; (2) traditional constrained optimization of low rank tensors as in [12]; (3) a mixture of low-rank tensors. [sent-41, score-0.531]
23 The above-mentioned work all addresses the tensor completion problem in which the locations of the missing entries are known, and moreover, observation noise is assumed to be Gaussian. [sent-42, score-0.553]
24 However, in practice, a fraction of the tensorial entries can be arbitrarily corrupted by some large errors, and the number and the locations of the corrupted entries are unknown. [sent-43, score-0.342]
25 [14] have extended the Robust Principal Component Analysis [9] from recovering a low-rank matrix to the tensor case. [sent-45, score-0.521]
26 More precisely, they have proposed a method to recover a low-rank tensor with sparse errors. [sent-46, score-0.513]
27 However, there are two issues that limit the practicality of such methods: (1) The tensorial data are assumed to be well aligned and rectified. [sent-47, score-0.124]
28 Inspired by the previous work and motivated by the above observations, we propose a more general method for the recovery of low-rank tensorial data, especially three-order tensorial data, since our main interests are visual data. [sent-49, score-0.356]
29 The main contributions of our work are three-fold: (1) The data samples in the tensor do not need to be well-aligned or rectified, and can be arbitrarily corrupted with a small fraction of errors. [sent-50, score-0.572]
30 (2) This framework can simultaneously perform rectification and alignment when applied to imagery data such as image sequences and video frames. [sent-51, score-0.206]
31 (3) To resolve the interdependence among the nuclear norms of the unfolding matrices, we introduce auxiliary variables and relax the hard equality constraints using the augmented Lagrange multiplier method. [sent-53, score-0.518]
32 To further improve the efficiency, we introduce a proximal gradient step to the alternating direction minimization method. [sent-54, score-0.151]
33 Lowercase letters (a, b, c · · · ) denote scalars; bold lowercase (a, b, c · · · ) letters denote vectors; capital letters (A, B, C · · · ) denote matrices; calligraphic letters (A, B, C · · · ) denote tensors. [sent-57, score-0.125]
34 In the following subsections, the tensor algebra and the tensor rank are briefly introduced. [sent-58, score-1.161]
35 2 I3 I3 I1 I2 I1 I2 I2 I2 A(1) I1 I3 I1 I2 I2 I3 I3 I3 A(2) I2 I3 I1 I2 I3 I1 I1 I1 A(3) Figure 1: Illustration of unfolding a 3-order tensor. [sent-59, score-0.25]
36 1 Tensor Algebra We denote an N -order tensor as A ∈ RI1 ×I2 ×···×IN , where In (n = 1, 2, . [sent-61, score-0.492]
37 Each element in this tensor is represented as ai1 ···in ···iN , where 1 ≤ in ≤ In . [sent-65, score-0.513]
38 Each order of a tensor is associated with a ‘mode’. [sent-66, score-0.492]
39 By unfolding a tensor along a mode, a tensor’s unfolding matrix corresponding to this mode is obtained. [sent-67, score-1.077]
40 For example, the mode-n unfolding matrix ∏ A(n) ∈ RIn ×( i̸=n Ii ) of A, represented as A(n) = unfoldn (A), consists of In -dimensional moden column vectors which are obtained by varying the nth-mode index in and keeping indices of the other modes fixed. [sent-68, score-0.321]
41 1 shows an illustration of unfolding a 3-order tensor. [sent-70, score-0.25]
42 The inverse operation of the mode-n unfolding is the mode-n folding which restores the original tensor A from the mode-n unfolding matrix A(n) , represented as A = foldn (A(n) ). [sent-71, score-1.042]
43 The mode-n rank rn of A is defined as the rank of the mode-n unfolding matrix A(n) : rn = rank(A(n) ). [sent-72, score-0.603]
44 The operation of mode-n product of a tensor and a matrix forms a new tensor. [sent-73, score-0.521]
45 The mode-n product of tensor A and matrix U is denoted as A ×n U . [sent-74, score-0.521]
46 (1) in ∑ ∑ The scalar product of two tensors A and B with the dimension is defined as ⟨A, B⟩ = i1 i2 · · √ ∑ · iN ai1 ···iN bi1 ···iN . [sent-77, score-0.184]
47 The l0 norm ||A||0 is defined to be the number of non-zero entries in A and the l1 norm ||A||1 = ∑ i1 ,. [sent-79, score-0.081]
48 2 Tensor Rank Traditionally, there are two definitions of tensor rank, which are based on PARAFAC decomposition [7] and Tucker decomposition [8], respectively. [sent-85, score-0.586]
49 However, this rank definition is a highly nonconvex and discontinuous function on the tensor space. [sent-91, score-0.685]
50 Another kind of rank definition considers the mode-n rank rn of tensors, which is inspired by the Tucker decomposition [8]. [sent-93, score-0.343]
51 The tensor A can be decomposed as follows: A = G ×1 U (1) ×2 U (2) · · · ×N U (N ) , ⊤ ⊤ ⊤ (3) where G = A ×1 U (1) ×2 U (2) · · · ×N U (N ) is the core tensor controlling the interaction between the N mode matrices U (1) , . [sent-94, score-1.102]
52 In the sense of Tucker decomposition, an appropriate definition of tensor rank should satisfy the follow condition: a low-rank tensor is a low-rank matrix when unfolded appropriately. [sent-98, score-1.181]
53 This means the rank of a tensor can be represented by the rank of the 3 tensor’s unfolding matrices. [sent-99, score-1.031]
54 As illustrated in [8], the orthonormal column vectors of U (n) span the column space of the mode-n unfolding matrix A(n) , (1 ≤ n ≤ N ), so that if U (n) ∈ RIn ×rn , n = 1, . [sent-100, score-0.321]
55 , N , then the rank of the mode-n unfolding matrix A(n) is rn . [sent-103, score-0.441]
56 We adopt this tensor rank definition in this paper. [sent-108, score-0.651]
57 3 Low-rank Structure Recovery for Tensors In this section, we first formulate the problem of recovering low-rank tensors despite deformation and corruption, and then introduce an iterative optimization method to solve the low-rank recovery problem. [sent-109, score-0.337]
58 1 Problem Formulation Without loss of generality, in this paper we focus on 3-order tensors to study the low-rank recovery problem. [sent-112, score-0.262]
59 Consider a low-rank 3-order data tensor A ∈ RI1 ×I2 ×I3 . [sent-114, score-0.492]
60 In real applications, the data are inevitably corrupted by noise or errors. [sent-115, score-0.08]
61 Based on the above assumptions, the original tensor data A can be represented as A = L + E, (4) where L is a low-rank tensor. [sent-117, score-0.513]
62 (4) is that it requires the tensor to be well aligned. [sent-121, score-0.492]
63 For real data such as video and face images, the image frames (face images) should be well aligned to ensure that the three-order tensor of the image stack to have low-rank. [sent-122, score-0.661]
64 , τI3 ∈ Rp (p is the dimension of the transformations) which act on the two-dimensional slices (matrices) of the tensor data1 . [sent-127, score-0.492]
65 When both corruption and misalignment are modeled, the low-rank structure recovery for tensors can be formalized as follows. [sent-136, score-0.287]
66 (6) L,E,Γ The above optimization problem is not directly tractable for the following two reasons: (1) both rank and ℓ0 -norm are nonconvex and discontinuous; (2) the equality constraint A ◦ Γ = L + E is highly nonlinear due to the domain transformation Γ. [sent-140, score-0.252]
67 To relax the limitation (1), we first recall the tensor rank definition in Section 2. [sent-141, score-0.656]
68 In our work, we adopt the rank definition based on the Tucker decomposition which can be represented as follows: L is a rank-(r1 , r2 , r3 ) tensor where ri is the rank of unfolding matrix L(i) . [sent-143, score-1.132]
69 In this way, tensor rank can be converted to calculating a set of matrices’ rank. [sent-144, score-0.626]
70 We know that the nuclear (or trace) norm is ∑m the convex envelop of the rank of matrix: ||L(i) ||∗ = k=1 σk (L(i) ), where σk (L(i) ) is kth singular value of matrix L(i) . [sent-145, score-0.247]
71 Therefore, we define the nuclear norm of a three-order tensor as follows: ||L||∗ = N ∑ αi ||L(i) ||∗ , N = 3. [sent-146, score-0.576]
72 The rank of L is replaced by ||L||∗ to make a convex relaxation of the optimization problem. [sent-148, score-0.163]
73 It is well know that 1 In most applications, a three-order tensor can be naturally partitioned into a set of matrices (such as image frames in a video) and transformations should be applied on these matrices 4 ℓ1 -norm is a good convex surrogate of the ℓ0 -norm. [sent-149, score-0.724]
74 2 Optimization Algorithm Although the problem in (9) is convex, it is still difficult to solve due to the interdependent nuclear norm terms. [sent-159, score-0.109]
75 To remove these interdependencies and to optimize these terms independently, we introduce three auxiliary matrices {Mi , i = 1, 2, 3} to replace {L(i) , i = 1, 2, 3}, and the optimization problem changes to 3 ∑ ˜ min αi ||Mi ||∗ + γ||E||1 s. [sent-160, score-0.112]
76 Y and Qi are the Lagrange multiplier tensor and matrix respectively. [sent-165, score-0.593]
77 n ∑ ˜ ∆Γk+1 = Ji+ (∆Γk+1 )⊤ ϵi ϵ⊤ , i (3) i=1 ˜ where Ji+ = (Ji⊤ Ji )−1 Ji⊤ is pseudo-inverse of Ji and (∆Γk+1 )(3) is the mode-3 unfolding ˜k+1 . [sent-179, score-0.25]
78 matrix of tensor ∆Γ • For terms Y k+1 and Qk+1 : i Y k+1 = Y k − T k+1 /µ; Qk+1 = Qk − (Lk+1 − Mik+1 )/µ, i i (i) i = 1, 2, 3. [sent-180, score-0.521]
79 Consider the mode3 unfolding matrix A(3) in the bottom row of Fig. [sent-189, score-0.279]
80 Suppose the tensor is formed by stacking a set of images along the third mode. [sent-191, score-0.565]
81 While for the mode-1 and mode-2 unfolding matrices (see Fig. [sent-193, score-0.312]
82 RASL: In the image alignment applications, RASL treats each image as a vector and does not make use of any spatial structure within each image. [sent-200, score-0.213]
83 1, in our work, the low-rank constraint on the mode-1 and mode-2 unfolding matrices effectively harnesses the spatial structures within images. [sent-202, score-0.453]
84 TILT: TILT deals with only one image and harnesses spatial low-rank structures to rectify the image. [sent-205, score-0.225]
85 Moreover, since RASL is applied to one mode of the tensor, to make it more competitive, we apply RASL to each mode of the tensor and take the mode that has the minimal reconstruction error. [sent-224, score-0.691]
86 For synthetic data, we first randomly generate two data tensors: (1) a pure low-rank tensor Lo ∈ R50×50×50 whose rank is (10,10,10); (2) an error tensor E ∈ R50×50×50 in which only a fraction c of entries are non-zero (To ensure the error to be sparse, the maximal value of c is set to 40%). [sent-225, score-1.174]
87 Then the testing tensor A can be obtained as A = Lo + E. [sent-226, score-0.492]
88 The above results demonstrate the effectiveness and efficiency of our proposed optimization method for low-rank tensor recovery. [sent-238, score-0.521]
89 The first dataset contains 16 images of the side of a building, taken from various viewpoints by a perspective camera, and with various occlusions due to tree branches. [sent-241, score-0.101]
90 3 illustrates the low-rank recovery results on this data set, in which Fig. [sent-243, score-0.078]
91 The second data set contains 100 images of the handwritten number “3”, with a fair amount of diversity. [sent-254, score-0.073]
92 5, the face alignment results obtained by our work is significantly better than those obtained by the other two algorithms. [sent-262, score-0.129]
93 The reason is that human face has a rich spatial low-rank structures due to symmetry, and our method simultaneously harnesses both temporal and spatial low-rank structures for rectification and alignment. [sent-263, score-0.28]
94 5 Conclusion We have in this paper proposed a general low-rank recovery framework for arbitrary tensor data, which can simultaneously realize rectification and alignment. [sent-264, score-0.622]
95 We have adopted a proximal gradient based alternating direction method to solve the optimization problem, and have shown that the convergence of our algorithm is guaranteed. [sent-265, score-0.158]
96 Learned-Miller, “Unsupervised joint alignment of complex images”, International Conference on Computer Vision pp. [sent-278, score-0.104]
97 Kruskal, “Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics”, Linear Algebra and its Applications, 18(2): 95-138, 1977. [sent-302, score-0.134]
98 Kashima, “Estimation of low-rank tensors via convex optimization”, Technical report, arXiv:1010. [sent-329, score-0.184]
99 Ma, “The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices”, Technical Report UILU-ENG-09-2215, UIUC Technical Report, 2009. [sent-341, score-0.362]
100 Yuan, “Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization”, Mathematics of Computation, 82(281): 301-329, 2013. [sent-344, score-0.23]
wordName wordTfidf (topN-words)
[('rasl', 0.57), ('tensor', 0.492), ('unfolding', 0.25), ('tensors', 0.184), ('tilt', 0.154), ('mik', 0.151), ('rank', 0.134), ('tensorial', 0.124), ('recti', 0.124), ('lk', 0.123), ('qk', 0.115), ('alignment', 0.104), ('mi', 0.086), ('alm', 0.083), ('corrupted', 0.08), ('recovery', 0.078), ('apgp', 0.076), ('ji', 0.074), ('images', 0.073), ('multiplier', 0.072), ('lagrange', 0.07), ('tucker', 0.067), ('li', 0.064), ('matrices', 0.062), ('augmented', 0.062), ('nuclear', 0.058), ('lo', 0.058), ('apg', 0.058), ('harnesses', 0.057), ('ialm', 0.057), ('mode', 0.056), ('structures', 0.051), ('proximal', 0.049), ('decomposition', 0.047), ('rectify', 0.046), ('parafac', 0.046), ('deformation', 0.046), ('algebra', 0.043), ('videos', 0.042), ('ranks', 0.039), ('deformed', 0.038), ('foldi', 0.038), ('misalignments', 0.038), ('rin', 0.038), ('image', 0.038), ('alternating', 0.036), ('transformations', 0.036), ('oi', 0.036), ('qi', 0.034), ('frames', 0.034), ('video', 0.034), ('linearized', 0.034), ('unfolded', 0.034), ('spatial', 0.033), ('nonconvex', 0.033), ('completion', 0.032), ('reconstruction', 0.031), ('harness', 0.031), ('transformation', 0.031), ('relax', 0.03), ('visual', 0.03), ('simultaneously', 0.03), ('entries', 0.029), ('gandy', 0.029), ('textures', 0.029), ('lowercase', 0.029), ('matrix', 0.029), ('optimization', 0.029), ('rn', 0.028), ('viewpoints', 0.028), ('align', 0.028), ('ganesh', 0.028), ('uj', 0.027), ('ciency', 0.027), ('nition', 0.027), ('synthetic', 0.027), ('ma', 0.027), ('jn', 0.026), ('discontinuous', 0.026), ('norm', 0.026), ('interdependent', 0.025), ('face', 0.025), ('equality', 0.025), ('lagrangian', 0.025), ('adopt', 0.025), ('corruption', 0.025), ('arg', 0.024), ('letters', 0.024), ('decompositions', 0.023), ('direction', 0.023), ('lr', 0.022), ('realize', 0.022), ('minimization', 0.022), ('auxiliary', 0.021), ('recover', 0.021), ('gradient', 0.021), ('validated', 0.021), ('represented', 0.021), ('vision', 0.021), ('column', 0.021)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors
Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma
Abstract: In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efficiency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efficient and effective than previous work. The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms “RASL” and “TILT” can be viewed as two special cases of our work, and yet each only performs part of the function of our method.
2 0.42121699 11 nips-2013-A New Convex Relaxation for Tensor Completion
Author: Bernardino Romera-Paredes, Massimiliano Pontil
Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable. 1
3 0.34286919 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors
Author: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu
Abstract: Tensor completion from incomplete observations is a problem of significant practical interest. However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from O(nr log2 (n)) observations. For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results. 1
4 0.29635686 74 nips-2013-Convex Tensor Decomposition via Structured Schatten Norm Regularization
Author: Ryota Tomioka, Taiji Suzuki
Abstract: We study a new class of structured Schatten norms for tensors that includes two recently proposed norms (“overlapped” and “latent”) for convex-optimizationbased tensor decomposition. We analyze the performance of “latent” approach for tensor decomposition, which was empirically found to perform better than the “overlapped” approach in some settings. We show theoretically that this is indeed the case. In particular, when the unknown true tensor is low-rank in a specific unknown mode, this approach performs as well as knowing the mode with the smallest rank. Along the way, we show a novel duality result for structured Schatten norms, which is also interesting in the general context of structured sparsity. We confirm through numerical simulations that our theory can precisely predict the scaling behaviour of the mean squared error. 1
5 0.29619852 155 nips-2013-Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition
Author: Tzu-Kuo Huang, Jeff Schneider
Abstract: Learning dynamic models from observed data has been a central issue in many scientific studies or engineering tasks. The usual setting is that data are collected sequentially from trajectories of some dynamical system operation. In quite a few modern scientific modeling tasks, however, it turns out that reliable sequential data are rather difficult to gather, whereas out-of-order snapshots are much easier to obtain. Examples include the modeling of galaxies, chronic diseases such Alzheimer’s, or certain biological processes. Existing methods for learning dynamic model from non-sequence data are mostly based on Expectation-Maximization, which involves non-convex optimization and is thus hard to analyze. Inspired by recent advances in spectral learning methods, we propose to study this problem from a different perspective: moment matching and spectral decomposition. Under that framework, we identify reasonable assumptions on the generative process of non-sequence data, and propose learning algorithms based on the tensor decomposition method [2] to provably recover firstorder Markov models and hidden Markov models. To the best of our knowledge, this is the first formal guarantee on learning from non-sequence data. Preliminary simulation results confirm our theoretical findings. 1
6 0.27724063 179 nips-2013-Low-Rank Matrix and Tensor Completion via Adaptive Sampling
7 0.23268056 203 nips-2013-Multilinear Dynamical Systems for Tensor Time Series
8 0.18676026 281 nips-2013-Robust Low Rank Kernel Embeddings of Multivariate Distributions
9 0.13511132 263 nips-2013-Reasoning With Neural Tensor Networks for Knowledge Base Completion
10 0.099226303 353 nips-2013-When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
11 0.098197147 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints
12 0.07720273 56 nips-2013-Better Approximation and Faster Algorithm Using the Proximal Average
13 0.075251564 70 nips-2013-Contrastive Learning Using Spectral Methods
14 0.074575201 222 nips-2013-On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization
15 0.072479382 307 nips-2013-Speedup Matrix Completion with Side Information: Application to Multi-Label Learning
16 0.071175121 185 nips-2013-Matrix Completion From any Given Set of Observations
17 0.063787453 254 nips-2013-Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms
18 0.061812565 286 nips-2013-Robust learning of low-dimensional dynamics from large neural ensembles
19 0.059615932 233 nips-2013-Online Robust PCA via Stochastic Optimization
20 0.059450451 300 nips-2013-Solving the multi-way matching problem by permutation synchronization
topicId topicWeight
[(0, 0.168), (1, 0.124), (2, 0.124), (3, 0.352), (4, 0.021), (5, -0.377), (6, 0.059), (7, -0.049), (8, 0.167), (9, 0.048), (10, -0.054), (11, -0.046), (12, -0.023), (13, 0.028), (14, -0.031), (15, -0.003), (16, -0.055), (17, -0.097), (18, 0.043), (19, 0.029), (20, 0.01), (21, 0.142), (22, -0.02), (23, 0.042), (24, -0.056), (25, 0.047), (26, 0.008), (27, 0.106), (28, 0.045), (29, 0.01), (30, 0.036), (31, 0.072), (32, -0.029), (33, 0.01), (34, -0.024), (35, -0.032), (36, -0.023), (37, 0.008), (38, -0.048), (39, 0.0), (40, 0.025), (41, -0.032), (42, 0.049), (43, 0.045), (44, -0.007), (45, -0.001), (46, 0.006), (47, 0.025), (48, 0.004), (49, -0.002)]
simIndex simValue paperId paperTitle
same-paper 1 0.95863748 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors
Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma
Abstract: In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efficiency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efficient and effective than previous work. The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms “RASL” and “TILT” can be viewed as two special cases of our work, and yet each only performs part of the function of our method.
2 0.90491587 11 nips-2013-A New Convex Relaxation for Tensor Completion
Author: Bernardino Romera-Paredes, Massimiliano Pontil
Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable. 1
3 0.90381855 203 nips-2013-Multilinear Dynamical Systems for Tensor Time Series
Author: Mark Rogers, Lei Li, Stuart Russell
Abstract: Data in the sciences frequently occur as sequences of multidimensional arrays called tensors. How can hidden, evolving trends in such data be extracted while preserving the tensor structure? The model that is traditionally used is the linear dynamical system (LDS) with Gaussian noise, which treats the latent state and observation at each time slice as a vector. We present the multilinear dynamical system (MLDS) for modeling tensor time series and an expectation–maximization (EM) algorithm to estimate the parameters. The MLDS models each tensor observation in the time series as the multilinear projection of the corresponding member of a sequence of latent tensors. The latent tensors are again evolving with respect to a multilinear projection. Compared to the LDS with an equal number of parameters, the MLDS achieves higher prediction accuracy and marginal likelihood for both artificial and real datasets. 1
4 0.85455352 74 nips-2013-Convex Tensor Decomposition via Structured Schatten Norm Regularization
Author: Ryota Tomioka, Taiji Suzuki
Abstract: We study a new class of structured Schatten norms for tensors that includes two recently proposed norms (“overlapped” and “latent”) for convex-optimizationbased tensor decomposition. We analyze the performance of “latent” approach for tensor decomposition, which was empirically found to perform better than the “overlapped” approach in some settings. We show theoretically that this is indeed the case. In particular, when the unknown true tensor is low-rank in a specific unknown mode, this approach performs as well as knowing the mode with the smallest rank. Along the way, we show a novel duality result for structured Schatten norms, which is also interesting in the general context of structured sparsity. We confirm through numerical simulations that our theory can precisely predict the scaling behaviour of the mean squared error. 1
5 0.84267288 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors
Author: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu
Abstract: Tensor completion from incomplete observations is a problem of significant practical interest. However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from O(nr log2 (n)) observations. For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results. 1
6 0.68456215 155 nips-2013-Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition
7 0.59979469 179 nips-2013-Low-Rank Matrix and Tensor Completion via Adaptive Sampling
8 0.45329201 281 nips-2013-Robust Low Rank Kernel Embeddings of Multivariate Distributions
9 0.39838836 263 nips-2013-Reasoning With Neural Tensor Networks for Knowledge Base Completion
10 0.37088317 70 nips-2013-Contrastive Learning Using Spectral Methods
11 0.31740415 254 nips-2013-Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms
13 0.31083632 222 nips-2013-On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization
14 0.30655283 117 nips-2013-Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis
15 0.30229339 342 nips-2013-Unsupervised Spectral Learning of Finite State Transducers
16 0.29674715 307 nips-2013-Speedup Matrix Completion with Side Information: Application to Multi-Label Learning
17 0.29571539 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints
18 0.27925691 214 nips-2013-On Algorithms for Sparse Multi-factor NMF
19 0.26123458 185 nips-2013-Matrix Completion From any Given Set of Observations
20 0.25017986 354 nips-2013-When in Doubt, SWAP: High-Dimensional Sparse Recovery from Correlated Measurements
topicId topicWeight
[(16, 0.029), (33, 0.165), (34, 0.08), (41, 0.062), (49, 0.042), (56, 0.113), (70, 0.04), (80, 0.23), (85, 0.045), (89, 0.027), (93, 0.039), (95, 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 0.80913037 295 nips-2013-Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors
Author: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma
Abstract: In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efficiency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efficient and effective than previous work. The proposed method can be easily applied to simultaneously rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms “RASL” and “TILT” can be viewed as two special cases of our work, and yet each only performs part of the function of our method.
2 0.80781949 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 finding 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 finds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efficient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods. 1
3 0.70977074 11 nips-2013-A New Convex Relaxation for Tensor Completion
Author: Bernardino Romera-Paredes, Massimiliano Pontil
Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable. 1
4 0.7075237 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives
Author: Mehrdad Mahdavi, Tianbao Yang, Rong Jin
Abstract: In this paper, we are interested in the development of efficient algorithms for convex optimization problems in the simultaneous presence of multiple objectives and stochasticity in the first-order information. We cast the stochastic multiple objective optimization problem into a constrained optimization problem by choosing one function as the objective and try to bound other objectives by appropriate thresholds. We first examine a two stages exploration-exploitation based algorithm which first approximates the stochastic objectives by sampling and then solves a constrained stochastic optimization problem by projected gradient method. This method attains a suboptimal convergence rate even under strong assumption on the objectives. Our second approach is an efficient primal-dual stochastic algorithm. It leverages on the theory of Lagrangian method √ conin strained optimization and attains the optimal convergence rate of O(1/ T ) in high probability for general Lipschitz continuous objectives.
5 0.70439345 333 nips-2013-Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent
Author: Tianbao Yang
Abstract: We present and study a distributed optimization algorithm by employing a stochastic dual coordinate ascent method. Stochastic dual coordinate ascent methods enjoy strong theoretical guarantees and often have better performances than stochastic gradient descent methods in optimizing regularized loss minimization problems. It still lacks of efforts in studying them in a distributed framework. We make a progress along the line by presenting a distributed stochastic dual coordinate ascent algorithm in a star network, with an analysis of the tradeoff between computation and communication. We verify our analysis by experiments on real data sets. Moreover, we compare the proposed algorithm with distributed stochastic gradient descent methods and distributed alternating direction methods of multipliers for optimizing SVMs in the same distributed framework, and observe competitive performances. 1
6 0.70412487 236 nips-2013-Optimal Neural Population Codes for High-dimensional Stimulus Variables
7 0.69989932 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing
8 0.69945443 304 nips-2013-Sparse nonnegative deconvolution for compressive calcium imaging: algorithms and phase transitions
9 0.69904989 45 nips-2013-BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
10 0.69850892 113 nips-2013-Exact and Stable Recovery of Pairwise Interaction Tensors
11 0.69837475 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
12 0.69817042 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances
13 0.69713986 22 nips-2013-Action is in the Eye of the Beholder: Eye-gaze Driven Model for Spatio-Temporal Action Localization
14 0.69695318 20 nips-2013-Accelerating Stochastic Gradient Descent using Predictive Variance Reduction
15 0.69685364 318 nips-2013-Structured Learning via Logistic Regression
16 0.69684082 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic
17 0.69630241 301 nips-2013-Sparse Additive Text Models with Low Rank Background
18 0.69584692 275 nips-2013-Reservoir Boosting : Between Online and Offline Ensemble Learning
19 0.69489193 149 nips-2013-Latent Structured Active Learning
20 0.69439435 36 nips-2013-Annealing between distributions by averaging moments