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

232 nips-2013-Online PCA for Contaminated Data

Source: pdf

Author: Jiashi Feng, Huan Xu, Shie Mannor, Shuicheng Yan

Abstract: We consider the online Principal Component Analysis (PCA) where contaminated samples (containing outliers) are revealed sequentially to the Principal Components (PCs) estimator. Due to their sensitiveness to outliers, previous online PCA algorithms fail in this case and their results can be arbitrarily skewed by the outliers. Here we propose the online robust PCA algorithm, which is able to improve the PCs estimation upon an initial one steadily, even when faced with a constant fraction of outliers. We show that the ﬁnal result of the proposed online RPCA has an acceptable degradation from the optimum. Actually, under mild conditions, online RPCA achieves the maximal robustness with a 50% breakdown point. Moreover, online RPCA is shown to be efﬁcient for both storage and computation, since it need not re-explore the previous samples as in traditional robust PCA algorithms. This endows online RPCA with scalability for large scale data. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 sg Abstract We consider the online Principal Component Analysis (PCA) where contaminated samples (containing outliers) are revealed sequentially to the Principal Components (PCs) estimator. [sent-10, score-0.437]

2 Due to their sensitiveness to outliers, previous online PCA algorithms fail in this case and their results can be arbitrarily skewed by the outliers. [sent-11, score-0.287]

3 Here we propose the online robust PCA algorithm, which is able to improve the PCs estimation upon an initial one steadily, even when faced with a constant fraction of outliers. [sent-12, score-0.471]

4 We show that the ﬁnal result of the proposed online RPCA has an acceptable degradation from the optimum. [sent-13, score-0.254]

5 Actually, under mild conditions, online RPCA achieves the maximal robustness with a 50% breakdown point. [sent-14, score-0.342]

6 Moreover, online RPCA is shown to be efﬁcient for both storage and computation, since it need not re-explore the previous samples as in traditional robust PCA algorithms. [sent-15, score-0.426]

7 This endows online RPCA with scalability for large scale data. [sent-16, score-0.264]

8 1 Introduction In this paper, we investigate the problem of robust Principal Component Analysis (PCA) in an online fashion. [sent-17, score-0.348]

9 PCA aims to construct a low-dimensional subspace based on a set of principal components (PCs) to approximate all the observed samples in the least-square sense [19]. [sent-18, score-0.234]

10 To address this problem, several online PCA algorithms have been developed in literature [15, 23, 10]. [sent-20, score-0.237]

11 For online PCA, at each time instance, a new sample is revealed, and the PCs estimation is updated accordingly without having to re-explore all previous samples. [sent-21, score-0.294]

12 Signiﬁcant advantages of online PCA algorithms include independence of their storage space requirement of the number of samples, and handling newly revealed samples quite efﬁciently. [sent-22, score-0.423]

13 However, all of these methods work in batch mode and cannot handle sequentially revealed samples in the online learning framework. [sent-25, score-0.529]

14 1 In this work, we propose a novel online Robust PCA algorithm to handle contaminated sample set, i. [sent-30, score-0.301]

15 , sample set that comprises both authentic samples (non-corrupted samples) and outliers (corrupted samples), which are revealed sequentially to the algorithm. [sent-32, score-0.671]

16 Previous online PCA algorithms generally fail in this case, since they update the PCs estimation through minimizing the quadratic error w. [sent-33, score-0.289]

17 The outliers may manipulate the PCs estimation severely and the result can be arbitrarily bad. [sent-37, score-0.33]

18 In contrast, the proposed online RPCA is shown to be robust to the outliers. [sent-38, score-0.365]

19 This is different from previous online PCA methods, where each and every new sample is admitted. [sent-40, score-0.258]

20 The probabilistic admittion/rejection procedure endows online RPCA with the ability to reject more outliers than authentic samples and thus alleviates the affect of outliers and robustiﬁes the PCs estimation. [sent-41, score-1.111]

21 Indeed, we show that given a proper initial estimation, online RPCA is able to steadily improve its output until convergence. [sent-42, score-0.319]

22 In fact, under mild conditions, online RPCA can be resistent to 50% outliers, namely having a 50% breakdown point. [sent-44, score-0.335]

23 Compared with previous robust PCA methods (typically works in batch mode), online RPCA only needs to maintain a covariance matrix whose size is independent of the number of data points. [sent-46, score-0.483]

24 Upon accepting a newly revealed sample, online RPCA updates the PCs estimation accordingly without re-exploring the previous samples. [sent-47, score-0.405]

25 Thus, online RPCA can deal with large amounts of data with low storage expense. [sent-48, score-0.258]

26 To the best of our knowledge, this is the ﬁrst attempt to make online PCA work for outlier-corrupted data, with theoretical performance guarantees. [sent-50, score-0.237]

27 To address this issue, different online learning techniques have been proposed, for example [1, 8], and many others. [sent-52, score-0.237]

28 Most of current online PCA methods perform the PCs estimation in an incremental manner [8, 18, 25]. [sent-53, score-0.325]

29 Recently, a randomized online PCA algorithm was proposed by [23], whose objective is to minimize the total expected quadratic error minus the total error of the batch algorithm (i. [sent-56, score-0.384]

30 However, none of these online PCA algorithms is robust to the outliers. [sent-59, score-0.348]

31 However, none of them can be directly applied in online learning setting. [sent-65, score-0.237]

32 In [15], an incremental and robust subspace learning method is proposed. [sent-70, score-0.217]

33 In this work, the authors focused on the case where the outliers can be modeled as sparse vectors. [sent-77, score-0.275]

34 However, they also focus on a different case from ours where the outliers are sparse vectors. [sent-82, score-0.275]

35 1 The Algorithm Problem Setup Given a set of observations {y1 , · · · , yT } (here T can be ﬁnite or inﬁnite) which are revealed sequentially, the goal of online PCA is to estimate and update the principal components (PCs) based on the newly revealed sample yt at time instance t. [sent-84, score-0.637]

36 Here, the observations are the mixture of authentic samples (non-corrupted samples) and outliers (corrupted samples). [sent-85, score-0.582]

37 The authentic samples zi ∈ Rp are generated through a linear mapping: zi = Axi + ni . [sent-86, score-0.43]

38 The outliers are denoted as oi ∈ Rp and in particular they are deﬁned as follows. [sent-100, score-0.513]

39 j In the above deﬁnition, we assume that the basis wj and outliers o are both normalized (see Algorithm 1 step 1)-a) where all the samples are 2 -normalized). [sent-108, score-0.618]

40 In this work, we are interested in the case where the outliers are mixed with authentic samples uniformly in the data stream, i. [sent-112, score-0.55]

41 The input to the proposed online RPCA algorithm is the sequence of observations Y = {y1 , y2 , · · · , yT }, which is the union of authentic samples Z = {zi } generated by the aforementioned linear model and outliers O = {oi }. [sent-115, score-0.836]

42 At the time instance t, online RPCA chooses a set of principal components {wj }d . [sent-118, score-0.36]

43 d T T j=1 wj AA wj Here, wj denotes the true principal components of matrix A. [sent-124, score-0.981]

44 2 Online Robust PCA Algorithm The details of the proposed online RPCA algorithm are shown in Algorithm 1. [sent-136, score-0.254]

45 Since the authentic samples and outliers are mixed uniformly, the outlier fraction in each batch is also λ. [sent-142, score-0.829]

46 Namely, in each batch Bi , there are (1 − λ)b authentic samples and λb outliers. [sent-143, score-0.386]

47 Since the algorithm only involves standard PCA computation, we can employ any incremental or online PCA method [8, 15] to update the PCs estimation upon accepting a new sample. [sent-145, score-0.365]

48 In the algorithm, the initial PC estimation can be obtained through standard PCA or robust PCA [24] on a mini batch of the samples. [sent-148, score-0.307]

49 Perform PCA on the ﬁrst batch B0 and obtain the initial principal compo(0) nent {wj }d . [sent-158, score-0.255]

50 (t) d j=1 b) Calculate the variance of yi along the direction w(t−1) : δi = (t−1) T wj 2 (t) yi . [sent-166, score-0.368]

51 j=1 (t) ∗ 3) Update the PC as wj = wj , ∀j = 1, . [sent-171, score-0.572]

52 We now explain the intuition of the proposed online RPCA algorithm. [sent-177, score-0.254]

53 Given an initial solution w(0) which is “closer” to the true PC directions than to the outlier direction 1 , the authentic samples will have larger variance along the current PC direction than outliers. [sent-178, score-0.472]

54 Thus in the probabilistic data selection process (as shown in Algorithm 1 step b) to step d)), authentic samples are more likely to be accepted than outliers. [sent-179, score-0.333]

55 Therefore, in the following PC updating based on standard PCA on the accepted data, authentic samples will contribute more than the outliers. [sent-181, score-0.357]

56 4 Main Results In this section we present the theoretical performance guarantee of the proposed online RPCA al(t) gorithm (Algorithm 1). [sent-184, score-0.254]

57 In the sequel, wj is the solution at the t-th time instance. [sent-185, score-0.304]

58 of the true princid pal component wj is j=1 wT AT Awj = 1. [sent-188, score-0.312]

59 2 1) 2 1) (c1 (1 − 2 ) − 4 + −4 2 − λb i=1 c2 (0) T d oi )2 (1 j=1 (wj (1 − λ)b(1 − 2 ) − Γo ) . [sent-195, score-0.238]

60 When the outliers vanish, the second term in the square root of performance H(w(t) ) is zero. [sent-198, score-0.275]

61 To further investigate the behavior of the proposed online RPCA in presence of outliers, we consider the following noiseless case. [sent-208, score-0.287]

62 When the outliers are distributed on the groundtruth subspace, i. [sent-216, score-0.335]

63 , λb d d j=1 |wT oi |2 = 1, the j (0) T conditions become i=1 j=1 (w oi )2 < ∞ and H(w(0) ) ≥ 0. [sent-218, score-0.476]

64 When the outliers are orthogonal to the groundtruth subspace, i. [sent-221, score-0.335]

65 , the conditions for the initial solution becomes H0 ≥ 1/2 − 1/4 − λb i=1 λb i=1 (0) T d oi )2 /(1 j=1 (wj d j=1 |wT oi |2 = 0, j T |w(0) j oi |2 ≤ b(1 − λ)/4, and − λ)b. [sent-223, score-0.781]

66 Hence, when the outlier fraction λ increases, the initial solution should be further away from outliers. [sent-224, score-0.235]

67 When 0 < least 2 d j=1 1/4 − |wT oi |2 < 1, the performance of online RPCA is improved by at j λb i=1 (0) T d oi )2 (1 j=1 (wj − Γo )/(1 − λ)b from its initial solution. [sent-226, score-0.762]

68 Hence, when the initial solution is further away from the outliers, the outlier fraction is smaller, or the outliers are closer to groundtruth subspace, the improvement is more signiﬁcant. [sent-227, score-0.57]

69 5, the performance of online RPCA still has a positive lower bound. [sent-229, score-0.237]

70 Therefore, the breakdown point of online RPCA is 50%, the highest that any algorithm can achieve. [sent-230, score-0.297]

71 These batch methods are able to provide initial estimate with performance guarantee, which may satisfy the initial condition. [sent-233, score-0.209]

72 5 Proof of The Results We brieﬂy explain the proof of Theorem 1: we ﬁrst show that when the PCs estimation is being improved, the variance of outliers along the PCs will keep decreasing. [sent-234, score-0.311]

73 Given the result in Lemma 1 , we obtain that the authentic samples concentration properties as stated in the following lemma [24]. [sent-251, score-0.342]

74 We denote the set of accepted authentic samples as Zt and the set of accepted outliers as Ot from the t-th small batch. [sent-260, score-0.666]

75 In the following lemma, we provide the estimation of number of accepted authentic samples |Zt | and outliers |Ot |. [sent-261, score-0.644]

76 For the current obtained principal components {wj authentic samples |Zt | and outliers |Ot | satisfy |Zt | 1 − b b (1−λ)b d (t−1) T (wj i=1 zi )2 ≤ δ and j=1 |Ot | 1 − b b λb d the number of the accepted (t−1) T (wj oi )2 ≤ δ i=1 j=1 2 with probability at least 1 − e−2δ b . [sent-263, score-1.039]

77 In the following lemma, we show that when the algorithm improves the PCs estimation, the impact of outliers will be decreased accordingly. [sent-266, score-0.292]

78 For an outlier oi , an arbitrary orthogonal basis {wj }d and the groundtruth basis j=1 d d d d T T {wj }d which satisfy that j=1 wj oi ≥ wT oi and j=1 wT wj ≥ j j j=1 j=1 j=1 wj oi , the value of d j=1 T wj oi is a monotonically decreasing function of d j=1 w T wj . [sent-268, score-2.81]

79 6 Simulations The numerical study is aimed to illustrate the performance of online robust PCA algorithm. [sent-271, score-0.348]

80 Since it is hard to determine the most adversarial outlier distribution, in simulations, we generate the outliers concentrate on several directions deviating from the groundtruth subspace. [sent-274, score-0.481]

81 This makes a rather adversarial case and is suitable for investigating the robustness of the proposed online RPCA algorithm. [sent-275, score-0.295]

82 Simulation results for p = 100, d = 1, s = 2 and outliers distributed on one direction are shown in Figure 1. [sent-279, score-0.275]

83 5 seconds for the proposed online RPCA to process 10, 000 samples of 100 dimensional, on a PC with Quad CPU with 2. [sent-281, score-0.311]

84 Firstly, online RPCA can improve the PC estimation steadily. [sent-289, score-0.273]

85 Secondly, the performance of online RPCA is rather robust to outliers. [sent-293, score-0.348]

86 To more clearly demonstrate the robustness of online RPCA to outliers, we implement the online PCA proposed in [23] as baseline for the σ = 2 case. [sent-300, score-0.516]

87 The results are presented in Figure 1, from which we can observe that the performance of online PCA drops due to the sensitiveness to newly coming outliers. [sent-301, score-0.341]

88 1, the online PCA cannot recover the true PC directions and the performance is as low as 0. [sent-303, score-0.237]

89 2 50 0 0 10 30 20 # batches 40 50 Figure 1: Performance comparison of online RPCA (blue line) with online PCA (red line). [sent-360, score-0.567]

90 7 Conclusions In this work, we proposed an online robust PCA (online RPCA) algorithm for samples corrupted by outliers. [sent-363, score-0.45]

91 The online RPCA alternates between standard PCA for updating PCs and probabilistic selection of the new samples which alleviates the impact of outliers. [sent-364, score-0.357]

92 Theoretical analysis showed that the online RPCA could improve the PC estimation steadily and provided results with bounded deviation from the optimum. [sent-365, score-0.306]

93 To the best of our knowledge, this is the ﬁrst work to investigate such online robust PCA problem with theoretical performance guarantee. [sent-366, score-0.348]

94 The proposed online robust PCA algorithm can be applied to handle challenges imposed by the modern big data analysis. [sent-367, score-0.382]

95 A fast algorithm for robust principal components based on projection pursuit. [sent-394, score-0.234]

96 Robpca: a new approach to robust principal component analysis. [sent-443, score-0.232]

97 A fast method for robust principal components with applications to chemometrics. [sent-450, score-0.234]

98 Projection-pursuit approach to robust dispersion matrices and principal components: primary theory and monte carlo. [sent-455, score-0.206]

99 Recursive robust pca or recursive sparse recovery in large but structured noise. [sent-484, score-0.477]

100 Randomized online pca algorithms with regret bounds that are logarithmic in the dimension. [sent-503, score-0.585]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('rpca', 0.537), ('pca', 0.348), ('pcs', 0.287), ('wj', 0.286), ('outliers', 0.275), ('oi', 0.238), ('online', 0.237), ('authentic', 0.218), ('outlier', 0.13), ('batch', 0.111), ('robust', 0.111), ('principal', 0.095), ('batches', 0.093), ('pc', 0.073), ('zi', 0.07), ('revealed', 0.07), ('ot', 0.067), ('hrpca', 0.066), ('groundtruth', 0.06), ('breakdown', 0.06), ('accepted', 0.058), ('wt', 0.058), ('samples', 0.057), ('singapore', 0.056), ('subspace', 0.054), ('incremental', 0.052), ('sensitiveness', 0.05), ('initial', 0.049), ('lemma', 0.046), ('contaminated', 0.043), ('yi', 0.041), ('newly', 0.038), ('rousseeuw', 0.038), ('fraction', 0.038), ('estimation', 0.036), ('zt', 0.034), ('steadily', 0.033), ('noiseless', 0.033), ('observations', 0.032), ('feng', 0.031), ('sequentially', 0.03), ('yt', 0.03), ('croux', 0.029), ('followings', 0.029), ('jiashi', 0.029), ('components', 0.028), ('corrupted', 0.028), ('sd', 0.027), ('signal', 0.027), ('hubert', 0.027), ('endows', 0.027), ('component', 0.026), ('robustness', 0.025), ('mode', 0.024), ('accepting', 0.024), ('ece', 0.024), ('shie', 0.024), ('updating', 0.024), ('arxiv', 0.024), ('covariance', 0.024), ('rp', 0.023), ('lemmas', 0.022), ('alleviates', 0.022), ('yan', 0.022), ('xu', 0.021), ('sample', 0.021), ('concentration', 0.021), ('replacement', 0.021), ('storage', 0.021), ('mild', 0.02), ('tpami', 0.02), ('randomized', 0.019), ('noise', 0.019), ('severely', 0.019), ('sp', 0.019), ('mannor', 0.019), ('wd', 0.019), ('nal', 0.019), ('namely', 0.018), ('converges', 0.018), ('recursive', 0.018), ('solution', 0.018), ('removal', 0.017), ('sons', 0.017), ('impact', 0.017), ('sup', 0.017), ('national', 0.017), ('imposed', 0.017), ('proposed', 0.017), ('compressive', 0.016), ('preprint', 0.016), ('update', 0.016), ('ratio', 0.016), ('adversarial', 0.016), ('coming', 0.016), ('adopted', 0.015), ('theorem', 0.015), ('ni', 0.015), ('numerische', 0.015), ('pricai', 0.015)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999982 232 nips-2013-Online PCA for Contaminated Data

Author: Jiashi Feng, Huan Xu, Shie Mannor, Shuicheng Yan

2 0.41302031 233 nips-2013-Online Robust PCA via Stochastic Optimization

Author: Jiashi Feng, Huan Xu, Shuicheng Yan

Abstract: Robust PCA methods are typically based on batch optimization and have to load all the samples into memory during optimization. This prevents them from efﬁciently processing big data. In this paper, we develop an Online Robust PCA (OR-PCA) that processes one sample per time instance and hence its memory cost is independent of the number of samples, signiﬁcantly enhancing the computation and storage efﬁciency. The proposed OR-PCA is based on stochastic optimization of an equivalent reformulation of the batch RPCA. Indeed, we show that OR-PCA provides a sequence of subspace estimations converging to the optimum of its batch counterpart and hence is provably robust to sparse corruption. Moreover, OR-PCA can naturally be applied for tracking dynamic subspace. Comprehensive simulations on subspace recovering and tracking demonstrate the robustness and efﬁciency advantages of the OR-PCA over online PCA and batch RPCA methods. 1

3 0.2184713 158 nips-2013-Learning Multiple Models via Regularized Weighting

Author: Daniel Vainsencher, Shie Mannor, Huan Xu

Abstract: We consider the general problem of Multiple Model Learning (MML) from data, from the statistical and algorithmic perspectives; this problem includes clustering, multiple regression and subspace clustering as special cases. A common approach to solving new MML problems is to generalize Lloyd’s algorithm for clustering (or Expectation-Maximization for soft clustering). However this approach is unfortunately sensitive to outliers and large noise: a single exceptional point may take over one of the models. We propose a different general formulation that seeks for each model a distribution over data points; the weights are regularized to be sufﬁciently spread out. This enhances robustness by making assumptions on class balance. We further provide generalization bounds and explain how the new iterations may be computed efﬁciently. We demonstrate the robustness beneﬁts of our approach with some experimental results and prove for the important case of clustering that our approach has a non-trivial breakdown point, i.e., is guaranteed to be robust to a ﬁxed percentage of adversarial unbounded outliers. 1

4 0.21550415 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

5 0.17278947 188 nips-2013-Memory Limited, Streaming PCA

Author: Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain

Abstract: We consider streaming, one-pass principal component analysis (PCA), in the highdimensional regime, with limited memory. Here, p-dimensional samples are presented sequentially, and the goal is to produce the k-dimensional subspace that best approximates these points. Standard algorithms require O(p2 ) memory; meanwhile no algorithm can do better than O(kp) memory, since this is what the output itself requires. Memory (or storage) complexity is most meaningful when understood in the context of computational and sample complexity. Sample complexity for high-dimensional PCA is typically studied in the setting of the spiked covariance model, where p-dimensional points are generated from a population covariance equal to the identity (white noise) plus a low-dimensional perturbation (the spike) which is the signal to be recovered. It is now well-understood that the spike can be recovered when the number of samples, n, scales proportionally with the dimension, p. Yet, all algorithms that provably achieve this, have memory complexity O(p2 ). Meanwhile, algorithms with memory-complexity O(kp) do not have provable bounds on sample complexity comparable to p. We present an algorithm that achieves both: it uses O(kp) memory (meaning storage of any kind) and is able to compute the k-dimensional spike with O(p log p) samplecomplexity – the ﬁrst algorithm of its kind. While our theoretical analysis focuses on the spiked covariance model, our simulations show that our algorithm is successful on much more general models for the data. 1

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

7 0.11265843 120 nips-2013-Faster Ridge Regression via the Subsampled Randomized Hadamard Transform

8 0.11210357 261 nips-2013-Rapid Distance-Based Outlier Detection via Sampling

9 0.10628391 224 nips-2013-On the Sample Complexity of Subspace Learning

10 0.082165517 314 nips-2013-Stochastic Optimization of PCA with Capped MSG

11 0.081907868 301 nips-2013-Sparse Additive Text Models with Low Rank Background

12 0.081885427 324 nips-2013-The Fast Convergence of Incremental PCA

13 0.081487879 339 nips-2013-Understanding Dropout

14 0.075594433 65 nips-2013-Compressive Feature Learning

15 0.075219303 91 nips-2013-Dirty Statistical Models

16 0.07384146 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives

17 0.070451058 286 nips-2013-Robust learning of low-dimensional dynamics from large neural ensembles

18 0.067691036 153 nips-2013-Learning Feature Selection Dependencies in Multi-task Learning

19 0.066253386 256 nips-2013-Probabilistic Principal Geodesic Analysis

20 0.064101115 230 nips-2013-Online Learning with Costly Features and Labels

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.16), (1, 0.038), (2, 0.129), (3, 0.016), (4, -0.023), (5, 0.029), (6, -0.124), (7, 0.172), (8, -0.122), (9, -0.074), (10, -0.104), (11, 0.219), (12, 0.137), (13, 0.256), (14, 0.07), (15, -0.007), (16, 0.052), (17, -0.004), (18, 0.116), (19, -0.066), (20, 0.001), (21, 0.016), (22, -0.051), (23, -0.055), (24, 0.111), (25, 0.123), (26, 0.077), (27, 0.168), (28, -0.005), (29, 0.029), (30, 0.075), (31, 0.062), (32, -0.045), (33, 0.014), (34, 0.034), (35, -0.154), (36, -0.071), (37, -0.004), (38, -0.167), (39, -0.025), (40, -0.109), (41, -0.049), (42, 0.064), (43, -0.057), (44, 0.067), (45, -0.195), (46, 0.052), (47, -0.019), (48, -0.013), (49, 0.089)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97184092 232 nips-2013-Online PCA for Contaminated Data

Author: Jiashi Feng, Huan Xu, Shie Mannor, Shuicheng Yan

2 0.85759056 233 nips-2013-Online Robust PCA via Stochastic Optimization

Author: Jiashi Feng, Huan Xu, Shuicheng Yan

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

Author: Yuhong Guo

4 0.60777456 188 nips-2013-Memory Limited, Streaming PCA

Author: Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain

5 0.57559979 314 nips-2013-Stochastic Optimization of PCA with Capped MSG

Author: Raman Arora, Andy Cotter, Nati Srebro

Abstract: We study PCA as a stochastic optimization problem and propose a novel stochastic approximation algorithm which we refer to as “Matrix Stochastic Gradient” (MSG), as well as a practical variant, Capped MSG. We study the method both theoretically and empirically. 1

6 0.55762374 120 nips-2013-Faster Ridge Regression via the Subsampled Randomized Hadamard Transform

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

8 0.47906899 261 nips-2013-Rapid Distance-Based Outlier Detection via Sampling

9 0.44316021 158 nips-2013-Learning Multiple Models via Regularized Weighting

10 0.38442805 224 nips-2013-On the Sample Complexity of Subspace Learning

11 0.3818028 324 nips-2013-The Fast Convergence of Incremental PCA

12 0.36774534 117 nips-2013-Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis

13 0.35844558 275 nips-2013-Reservoir Boosting : Between Online and Offline Ensemble Learning

14 0.35642681 284 nips-2013-Robust Spatial Filtering with Beta Divergence

15 0.34275514 332 nips-2013-Tracking Time-varying Graphical Structure

16 0.33888206 80 nips-2013-Data-driven Distributionally Robust Polynomial Optimization

17 0.31140998 256 nips-2013-Probabilistic Principal Geodesic Analysis

18 0.30917755 187 nips-2013-Memoized Online Variational Inference for Dirichlet Process Mixture Models

19 0.29876894 259 nips-2013-Provable Subspace Clustering: When LRR meets SSC

20 0.29219735 163 nips-2013-Learning a Deep Compact Image Representation for Visual Tracking

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(10, 0.017), (16, 0.054), (33, 0.123), (34, 0.087), (36, 0.031), (41, 0.017), (47, 0.262), (49, 0.021), (56, 0.096), (70, 0.017), (85, 0.097), (89, 0.052), (93, 0.021), (95, 0.015)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.80932909 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 artiﬁcial and real datasets. 1

same-paper 2 0.74333048 232 nips-2013-Online PCA for Contaminated Data

Author: Jiashi Feng, Huan Xu, Shie Mannor, Shuicheng Yan

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

Author: Vincent Q. Vu, Juhee Cho, Jing Lei, Karl Rohe

Abstract: We propose a novel convex relaxation of sparse principal subspace estimation based on the convex hull of rank-d projection matrices (the Fantope). The convex problem can be solved efﬁciently using alternating direction method of multipliers (ADMM). We establish a near-optimal convergence rate, in terms of the sparsity, ambient dimension, and sample size, for estimation of the principal subspace of a general covariance matrix without assuming the spiked covariance model. In the special case of d = 1, our result implies the near-optimality of DSPCA (d’Aspremont et al. [1]) even when the solution is not rank 1. We also provide a general theoretical framework for analyzing the statistical properties of the method for arbitrary input matrices that extends the applicability and provable guarantees to a wide array of settings. We demonstrate this with an application to Kendall’s tau correlation matrices and transelliptical component analysis. 1

4 0.61868715 332 nips-2013-Tracking Time-varying Graphical Structure

Author: Erich Kummerfeld, David Danks

Abstract: Structure learning algorithms for graphical models have focused almost exclusively on stable environments in which the underlying generative process does not change; that is, they assume that the generating model is globally stationary. In real-world environments, however, such changes often occur without warning or signal. Real-world data often come from generating models that are only locally stationary. In this paper, we present LoSST, a novel, heuristic structure learning algorithm that tracks changes in graphical model structure or parameters in a dynamic, real-time manner. We show by simulation that the algorithm performs comparably to batch-mode learning when the generating graphical structure is globally stationary, and signiﬁcantly better when it is only locally stationary. 1

5 0.60775667 168 nips-2013-Learning to Pass Expectation Propagation Messages

Author: Nicolas Heess, Daniel Tarlow, John Winn

Abstract: Expectation Propagation (EP) is a popular approximate posterior inference algorithm that often provides a fast and accurate alternative to sampling-based methods. However, while the EP framework in theory allows for complex nonGaussian factors, there is still a signiﬁcant practical barrier to using them within EP, because doing so requires the implementation of message update operators, which can be difﬁcult and require hand-crafted approximations. In this work, we study the question of whether it is possible to automatically derive fast and accurate EP updates by learning a discriminative model (e.g., a neural network or random forest) to map EP message inputs to EP message outputs. We address the practical concerns that arise in the process, and we provide empirical analysis on several challenging and diverse factors, indicating that there is a space of factors where this approach appears promising. 1

6 0.6072396 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

7 0.60702664 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

8 0.60657877 7 nips-2013-A Gang of Bandits

9 0.60464537 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

10 0.60290462 233 nips-2013-Online Robust PCA via Stochastic Optimization

11 0.6007607 196 nips-2013-Modeling Overlapping Communities with Node Popularities

12 0.59991008 140 nips-2013-Improved and Generalized Upper Bounds on the Complexity of Policy Iteration

13 0.59859061 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

14 0.59504414 350 nips-2013-Wavelets on Graphs via Deep Learning

15 0.59481823 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks

16 0.59399468 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

17 0.59379905 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic

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

19 0.59051567 355 nips-2013-Which Space Partitioning Tree to Use for Search?

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