nips nips2011 nips2011-257 knowledge-graph by maker-knowledge-mining

257 nips-2011-SpaRCS: Recovering low-rank and sparse matrices from compressive measurements

Source: pdf

Author: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk

Abstract: We consider the problem of recovering a matrix M that is the sum of a low-rank matrix L and a sparse matrix S from a small set of linear measurements of the form y = A(M) = A(L + S). This model subsumes three important classes of signal recovery problems: compressive sensing, afﬁne rank minimization, and robust principal component analysis. We propose a natural optimization problem for signal recovery under this model and develop a new greedy algorithm called SpaRCS to solve it. Empirically, SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efﬁcient implementation. Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efﬁcacy of the algorithm. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We consider the problem of recovering a matrix M that is the sum of a low-rank matrix L and a sparse matrix S from a small set of linear measurements of the form y = A(M) = A(L + S). [sent-7, score-0.401]

2 This model subsumes three important classes of signal recovery problems: compressive sensing, afﬁne rank minimization, and robust principal component analysis. [sent-8, score-0.618]

3 We propose a natural optimization problem for signal recovery under this model and develop a new greedy algorithm called SpaRCS to solve it. [sent-9, score-0.334]

4 Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efﬁcacy of the algorithm. [sent-11, score-0.68]

5 1 Introduction The explosion of digital sensing technology has unleashed a veritable data deluge that has pushed current signal processing algorithms to their limits. [sent-12, score-0.157]

6 Not only are traditional sensing and processing algorithms increasingly overwhelmed by the sheer volume of sensor data, but storage and transmission of the data itself is also increasingly prohibitive without ﬁrst employing costly compression techniques. [sent-13, score-0.125]

7 This reality has driven much of the recent research on compressive data acquisition, in which data is acquired directly in a compressed format [1]. [sent-14, score-0.209]

8 Within this general paradigm, three important problem classes have received signiﬁcant recent attention: compressive sensing, afﬁne rank minimization, and robust principal component analysis (PCA). [sent-16, score-0.318]

9 Compressive sensing (CS): CS is concerned with the recovery a vector x that is sparse in some transform domain [1]. [sent-17, score-0.415]

10 This problem formulation is non-convex, CS recovery is typically accomplished either via convex relaxation or greedy approaches. [sent-20, score-0.328]

11 In the afﬁne rank minimization problem [14, 23], we observe the linear measurements y = A(L), where L is a low-rank matrix. [sent-22, score-0.17]

12 One important sub-problem is that of matrix completion [3, 5, 22], where A takes the form of a sampling operator. [sent-23, score-0.165]

13 1 Robust PCA: In the robust PCA problem [2, 8], we wish to decompose a matrix M into a low-rank matrix L and a sparse matrix S such that M = L + S. [sent-26, score-0.332]

14 Speciﬁcally, we aim to recover the entries of a matrix M in terms of a low-rank matrix L and sparse matrix S from a small set of compressive measurements y = A(L + S). [sent-32, score-0.584]

15 A ﬁrst application is the recovery of a video sequence obtained from a static camera observing a dynamic scene under changing illumination. [sent-34, score-0.37]

16 The changing illumination has low-rank properties, while the foreground innovations exhibit sparse structures [2]. [sent-36, score-0.098]

17 A second application is hyperspectral imaging, where each column of M is the vectorized image of a particular spectral band; a low-rank plus sparse model arises naturally due to material properties [7]. [sent-39, score-0.363]

18 A third application is robust matrix completion [11], which can be cast as a compressive low-rank and sparse recovery problem. [sent-40, score-0.717]

19 SpaRCS combines the best aspects of CoSaMP [20] for sparse vector recovery and ADMiRA [17] for low-rank matrix recovery. [sent-44, score-0.386]

20 2 Background Here we introduce the relevant background information regarding signal recovery from CS measurements, where our deﬁnition of signal is broadened to include both vectors and matrices. [sent-45, score-0.392]

21 We further provide background on incoherency between low-rank and sparse matrices. [sent-46, score-0.14]

22 Restricted isometry and rank-restricted isometry properties: Signal recovery for a K-sparse vector from CS measurements is possible when the measurement operator A obeys the so-called restricted isometry property (RIP) [4] with constant K (1 2 K )kxk2  kA(x)k2  (1 + 2 2 K )kxk2 , 8kxk0  K. [sent-47, score-0.68]

23 In the case of CS, the `0 norm is relaxed to the `1 norm; for low-rank matrices, the rank operator is relaxed to the nuclear norm. [sent-53, score-0.163]

24 In contrast, greedy algorithms [17, 20] operate iteratively on the signal measurements, constructing a basis for the signal and attempting signal recovery restricted to that basis. [sent-54, score-0.476]

25 We highlight the CoSaMP algorithm [20] for sparse vector recovery and the ADMiRA algorithm [17] for low-rank matrix recovery in this paper. [sent-56, score-0.628]

26 Both algorithms have strong convergence guarantees when the measurement operator A satisﬁes the appropriate RIP or RRIP condition, most notably exponential convergence to the true signal. [sent-57, score-0.259]

27 2 Matrix Incoherency: For matrix decomposition problems such as the Robust PCA problem or the problem deﬁned in (3) to have unique solutions, there must exist a degree of incoherence between the low-rank matrix L and the sparse matrix S. [sent-58, score-0.325]

28 It is known that the decomposition of a matrix into its low-rank and sparse components makes sense only when the low-rank matrix is not sparse and, similarly, when the sparse matrix is not low-rank. [sent-59, score-0.455]

29 1 (Uniformly bounded matrix [5]) An N ⇥ N matrix L of rank r is uniformly bounded if its singular vectors {uj , vj , 1  j  r} obey p kuj k1 , kvj k1  µB /N , with µB = O(1), where kxk1 denotes the largest entry in magnitude of x. [sent-63, score-0.253]

30 When µB is small (note that µB 1), this model for the low-rank matrix L ensures that its singular vectors are not sparse. [sent-64, score-0.101]

31 1 Thus, µB controls the sparsity of the matrix L by bounding the sparsity of its singular vectors. [sent-67, score-0.101]

32 A sufﬁcient model for a sparse matrix that is not low-rank is to assume that the support set ⌦ is uniform. [sent-68, score-0.17]

33 As shown in the work of Candes, et al [2] this model is equivalent to deﬁning the sparse support set ⌦ = {(i, j) : i,j = 1} with each i,j being an i. [sent-69, score-0.1]

34 3 SpaRCS: CS recovery of low-rank and sparse matrices We now present the SpaRCS algorithm to solve (P1) and disucss its empirical properties. [sent-73, score-0.347]

35 Assume that we are interested in a matrix M 2 RN1 ⇥N2 such that M = L + S, with rank(L)  r, L uniformly bounded with constant µB , and kSk0  K with support distributed uniformly. [sent-74, score-0.096]

36 Rp provides us with p compressive measurements y of M. [sent-76, score-0.276]

37 Given y = A(M)+e, where e denotes measurement b b b b noise, our goal is to estimate a low rank matrix L and a sparse matrix S such that y ⇡ A(L + S). [sent-81, score-0.438]

38 At each iteration, SpaRCS computes a signal proxy and then proceeds through four steps to update its estimates of L and S. [sent-84, score-0.091]

39 We use the notation supp(X; K) to denote the largest K-term support set of the matrix X. [sent-86, score-0.096]

40 This forms a natural basis for sparse signal approximation. [sent-87, score-0.132]

41 While CoSaMP and ADMiRA operate solely in the presence of the measurement noise, SpaRCS must estimate L in the presence of the residual error of S, and vice-versa. [sent-94, score-0.221]

42 Proving convergence for the algorithm in the presence of the additional residual terms is non-trivial; simply lumping these additional residual errors together with the measurement noise e is insufﬁcient for analysis. [sent-95, score-0.296]

43 r=5 r=10 r=15 r=20 r=25 Figure 1: Phase transitions for a recovery problem of size N1 = N2 = N = 512. [sent-103, score-0.242]

44 Black indicates recovery failure, while white indicates recovery success. [sent-105, score-0.484]

45 Support estimation for the sparse vector merely entails sorting the signal proxy magnitudes and choosing the largest 2K elements. [sent-110, score-0.165]

46 4 Figure 2 compares the performance of SpaRCS with two alternate recovery algorithms. [sent-111, score-0.264]

47 02N 2 and use permuted noiselets [12] for the measurement operator A. [sent-120, score-0.263]

48 As a ﬁrst experiment, we generate convergence plots for matrices with N = 128 and vary the measurement b b ratio p/N 2 from 0. [sent-121, score-0.23]

49 We then recover L and S and measure the recovered signal to noise ⇣ ⌘ kMkF c b b ratio (RSNR) for M = L + S via 20 log . [sent-124, score-0.164]

50 We measure the recovery time required by each algorithm to reach a residual error b b ky A(L+S)k2  5 ⇥ 10 4 . [sent-128, score-0.316]

51 These results are displayed in Figure 2(b), which demonstrate that kyk2 SpaRCS converges signiﬁcantly faster than the two other recovery methods. [sent-129, score-0.26]

52 (a) Performance for a problem with N = 128 for various values of the measurement ratio p/N 2 . [sent-138, score-0.172]

53 In all experiments, we use permuted noiselets for the measurement operator A; these provide both a fast transform as well as save memory, since we do not have to store A explicitly. [sent-143, score-0.263]

54 Video compressive sensing: The video CS problem is concerned with recovering multiple image frames of a video sequence from CS measurements [6,21,24]. [sent-144, score-0.492]

55 We consider a 128 ⇥ 128 ⇥ 201 video sequence consisting of a static background with a number of people moving in the foreground. [sent-145, score-0.118]

56 We aim to not only recover the original video but also separate the background and foreground. [sent-146, score-0.142]

57 We resize the data cube into a 1282 ⇥ 201 matrix M, where each column corresponds to a (vectorized) image frame. [sent-147, score-0.146]

58 The measurement operator A operates on each column of M independently, simulating acquisition using a single pixel camera [13]. [sent-148, score-0.269]

59 The results are displayed in Figure 3, where it can be seen that SpaRCS accurately estimates and separates the low-rank background and the sparse foreground. [sent-152, score-0.126]

60 Figure 4 shows recovery results on a more challenging sequence 5 (a) (b) (c) Figure 3: SpaRCS recovery results on a 128 ⇥ 128 ⇥ 201 video sequence. [sent-153, score-0.568]

61 The video sequence is reshaped into an N1 ⇥ N2 matrix with N1 = 1282 and N2 = 201. [sent-154, score-0.202]

62 The recovery is accurate in spite of the dB at Parameters measurement operator AVideo Col-only 128x128x201 working independently on each frame. [sent-161, score-0.47]

63 measurement matrix M per col = 2458 Overall K = 49398 Rank = 1 Rho = 0. [sent-162, score-0.212]

64 1637 (a) (b) Figure 4: SpaRCS recovery results on a 64 ⇥ 64 ⇥ 234 video sequence. [sent-165, score-0.326]

65 The video sequence is reshaped into an N1 ⇥N2 matrix with N1 = 642 and N2 = 234. [sent-166, score-0.202]

66 The recovery is accurate in spite of the changing illumination conditions. [sent-172, score-0.289]

67 In contrast to SpaRCS, existing video CS algorithms do not work well with dramatically changing illumination. [sent-174, score-0.108]

68 Hyperspectral compressive sensing: Low-rank/sparse decomposition has an important physical relevance in hyperspectral imaging [7]. [sent-175, score-0.451]

69 Here we consider a hyperspectral cube, which contains a vector of spectral information at each image pixel. [sent-176, score-0.234]

70 A measurement device such as [25] can provide compressive measurements of such a hyperspectral cube. [sent-177, score-0.613]

71 We employ SpaRCS on a hyperspectral cube of size 128 ⇥ 128 ⇥ 128 rearranged as a matrix of size 1282 ⇥ 128 such that each column corresponds to a different spectral band. [sent-178, score-0.342]

72 15 ⇥ 1282 ⇥ 128 total measurements of the entire data cube with r = 8, K = 3000. [sent-180, score-0.128]

73 Parameter mismatch: In Figure 6, we analyze the inﬂuence of incorrect selection of the parameters r using the hyperspectral data as an example. [sent-184, score-0.195]

74 We plot the recovered SNR that can be obtained at various levels of the measurement ratio p/(N1 N2 ) for both the case of r = 8 and r = 4. [sent-185, score-0.203]

75 An empirical rule-of-thumb for greedy recovery algorithms is that the number of measurements p should be 2–5 times the number of independent parameters. [sent-189, score-0.364]

76 6 (a) (b) (c) (d) Figure 5: SpaRCS recovery results on a 128 ⇥ 128 ⇥ 128 hyperspectral data cube. [sent-191, score-0.437]

77 The hyperspectral Datasize: 128x128x128 ⇥ N x 128 matrix. [sent-192, score-0.195]

78 Each image pane 2 Measurement matrix takes inner corresponds to= a different spectral K product(a) Ground truth. [sent-194, score-0.109]

79 9 dB (a) r=4 r=8 RSNR (dB) 30 (b) 25 20 15 5 (c) 10 N2/p 15 20 (d) Figure 6: Hyperspectral data recovery for various values of the rank r of the low-rank matrix L. [sent-208, score-0.394]

80 (d) Comparison of compression ratio (N1 N2 )/p and recovery SNR using r = 4 and r = 8. [sent-216, score-0.298]

81 Robust matrix completion: We apply SpaRCS to the robust matrix completion problem [11] min kLk⇤ + ksk1 subject to L⌦ + s = y (6) where s models outlier noise and ⌦ denotes the set of observed entries. [sent-218, score-0.342]

82 This problem can be cast as a compressive low-rank and sparse matrix recovery problem by using a sparse matrix S in place of the outlier noise s and realizing that the support of S is a subset of ⌦. [sent-219, score-0.803]

83 This enables recovery of both L and S from samples of their sum L + S. [sent-220, score-0.242]

84 Matrix completion under outlier noise [10,11] has received some attention and, in many ways, is the work that is closest to this paper. [sent-221, score-0.154]

85 Furthermore, [10] is tied to the case when A is a sampling operator; it is not immediately clear whether this analysis can extend to the more general case of (P1), where the sparse component cannot be modeled as outlier noise in the measurements. [sent-227, score-0.133]

86 5 −20 −3 10 −2 10 −1 K/p 10 0 10 −1 (a) Performance 1/1000 1/100 1/50 1/25 1/10 K/p 1/5 1/4 1/3 (b) Timing plot Figure 7: Comparison of several algorithms for the robust matrix completion problem. [sent-232, score-0.213]

87 (a) RSNR averaged over 10 Monte-Carlo runs for an N ⇥ N matrix completion problem with N = 128, r = 1, and p/N 2 = 0. [sent-233, score-0.165]

88 In our robust matrix completion experiments we compare SpaRCS with CS SVT, OptSpace [16] (a non-robust matrix completion algorithm), and a convex solution using CVX [15]. [sent-239, score-0.409]

89 5 Conclusion We have considered the problem of recovering low-rank and sparse matrices given only a few linear measurements. [sent-243, score-0.134]

90 Our proposed greedy algorithm, SpaRCS, is both fast and accurate even for large matrix sizes and enjoys strong empirical performance in its convergence to the true solution. [sent-244, score-0.131]

91 We have demonstrated the applicability of SpaRCS to video compressive sensing, hyperspectral imaging, and robust matrix completion. [sent-245, score-0.585]

92 Both low-rank and sparse matrices exhibit rich structure in practice, including low-rank Hankel matrices in system identiﬁcation and group sparsity in background subtraction. [sent-248, score-0.17]

93 This would be especially useful in applications such as video CS, where the measurement operator is typically constrained to operate on each image frame individually. [sent-250, score-0.334]

94 Quantitative robust uncertainty principles and optimally sparse decomposie tions. [sent-283, score-0.122]

95 Compressed sensing and robust recovery of low rank e matrices. [sent-390, score-0.471]

96 The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. [sent-425, score-0.265]

97 Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. [sent-434, score-0.296]

98 Cosamp: Iterative signal recovery from incomplete and inaccurate samples. [sent-445, score-0.3]

99 Guaranteed minimum rank solutions of linear matrix equations via nuclear norm minimization. [sent-473, score-0.17]

100 SpaRCS: Recovering low-rank and sparse matrices from compressive measurements. [sent-503, score-0.293]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('sparcs', 0.761), ('recovery', 0.242), ('cs', 0.216), ('hyperspectral', 0.195), ('compressive', 0.188), ('measurement', 0.142), ('cosamp', 0.103), ('sensing', 0.099), ('completion', 0.095), ('admira', 0.09), ('measurements', 0.088), ('snr', 0.088), ('video', 0.084), ('rank', 0.082), ('rsnr', 0.079), ('sparse', 0.074), ('cvx', 0.072), ('matrix', 0.07), ('optspace', 0.07), ('lk', 0.068), ('db', 0.065), ('sankaranarayanan', 0.063), ('operator', 0.063), ('supp', 0.061), ('signal', 0.058), ('residual', 0.053), ('apg', 0.048), ('robust', 0.048), ('klk', 0.048), ('kvec', 0.048), ('reshaped', 0.048), ('rrip', 0.048), ('cand', 0.045), ('imaging', 0.045), ('isometry', 0.042), ('sk', 0.041), ('cube', 0.04), ('chandrasekaran', 0.038), ('vectorized', 0.038), ('outlier', 0.038), ('background', 0.034), ('sanghavi', 0.034), ('greedy', 0.034), ('baraniuk', 0.033), ('bl', 0.033), ('proxy', 0.033), ('svd', 0.032), ('incoherency', 0.032), ('noiselets', 0.032), ('recons', 0.032), ('waters', 0.032), ('convex', 0.031), ('rip', 0.031), ('recovered', 0.031), ('singular', 0.031), ('matrices', 0.031), ('ratio', 0.03), ('arxiv', 0.029), ('recovering', 0.029), ('svds', 0.028), ('klkf', 0.028), ('acquisition', 0.027), ('convergence', 0.027), ('pca', 0.026), ('support', 0.026), ('compression', 0.026), ('operate', 0.026), ('permuted', 0.026), ('parrilo', 0.026), ('rice', 0.026), ('changing', 0.024), ('recover', 0.024), ('duarte', 0.024), ('timing', 0.024), ('phase', 0.023), ('spite', 0.023), ('decomposition', 0.023), ('corrupted', 0.023), ('preprint', 0.022), ('chen', 0.022), ('alternate', 0.022), ('bs', 0.022), ('ka', 0.022), ('fazel', 0.022), ('af', 0.022), ('wk', 0.021), ('relaxation', 0.021), ('ky', 0.021), ('compressed', 0.021), ('noise', 0.021), ('spectral', 0.02), ('il', 0.02), ('camera', 0.02), ('recht', 0.02), ('image', 0.019), ('obeys', 0.019), ('displayed', 0.018), ('incoherence', 0.018), ('nuclear', 0.018), ('column', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 257 nips-2011-SpaRCS: Recovering low-rank and sparse matrices from compressive measurements

Author: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk

2 0.14485508 264 nips-2011-Sparse Recovery with Brownian Sensing

Author: Alexandra Carpentier, Odalric-ambrym Maillard, Rémi Munos

Abstract: We consider the problem of recovering the parameter α ∈ RK of a sparse function f (i.e. the number of non-zero entries of α is small compared to the number K of features) given noisy evaluations of f at a set of well-chosen sampling points. We introduce an additional randomization process, called Brownian sensing, based on the computation of stochastic integrals, which produces a Gaussian sensing matrix, for which good recovery properties are proven, independently on the number of sampling points N , even when the features are arbitrarily non-orthogonal. Under the assumption that f is H¨ lder continuous with exponent at least √ we proo 1/2, vide an estimate α of the parameter such that �α − α�2 = O(�η�2 / N ), where � � η is the observation noise. The method uses a set of sampling points uniformly distributed along a one-dimensional curve selected according to the features. We report numerical experiments illustrating our method. 1

3 0.10560597 259 nips-2011-Sparse Estimation with Structured Dictionaries

Author: David P. Wipf

Abstract: In the vast majority of recent work on sparse estimation algorithms, performance has been evaluated using ideal or quasi-ideal dictionaries (e.g., random Gaussian or Fourier) characterized by unit ℓ2 norm, incoherent columns or features. But in reality, these types of dictionaries represent only a subset of the dictionaries that are actually used in practice (largely restricted to idealized compressive sensing applications). In contrast, herein sparse estimation is considered in the context of structured dictionaries possibly exhibiting high coherence between arbitrary groups of columns and/or rows. Sparse penalized regression models are analyzed with the purpose of ﬁnding, to the extent possible, regimes of dictionary invariant performance. In particular, a Type II Bayesian estimator with a dictionarydependent sparsity penalty is shown to have a number of desirable invariance properties leading to provable advantages over more conventional penalties such as the ℓ1 norm, especially in areas where existing theoretical recovery guarantees no longer hold. This can translate into improved performance in applications such as model selection with correlated features, source localization, and compressive sensing with constrained measurement directions. 1

4 0.10541181 297 nips-2011-Universal low-rank matrix recovery from Pauli measurements

Author: Yi-kai Liu

Abstract: We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefﬁcients. We show that almost all sets of O(rd log6 d) Pauli measurements satisfy the rankr restricted isometry property (RIP). This implies that M can be recovered from a ﬁxed (“universal”) set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley’s inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality. 1

5 0.10318542 203 nips-2011-On the accuracy of l1-filtering of signals with block-sparse structure

Author: Fatma K. Karzan, Arkadi S. Nemirovski, Boris T. Polyak, Anatoli Juditsky

Abstract: We discuss new methods for the recovery of signals with block-sparse structure, based on 1 -minimization. Our emphasis is on the efﬁciently computable error bounds for the recovery routines. We optimize these bounds with respect to the method parameters to construct the estimators with improved statistical properties. We justify the proposed approach with an oracle inequality which links the properties of the recovery algorithms and the best estimation performance. 1

6 0.098850533 209 nips-2011-Orthogonal Matching Pursuit with Replacement

7 0.096644774 239 nips-2011-Robust Lasso with missing and grossly corrupted observations

8 0.090468191 211 nips-2011-Penalty Decomposition Methods for Rank Minimization

9 0.079698108 73 nips-2011-Divide-and-Conquer Matrix Factorization

10 0.075270273 230 nips-2011-RTRMC: A Riemannian trust-region method for low-rank matrix completion

11 0.070164926 70 nips-2011-Dimensionality Reduction Using the Sparse Linear Model

12 0.066565581 165 nips-2011-Matrix Completion for Multi-label Image Classification

13 0.064493157 93 nips-2011-Extracting Speaker-Specific Information with a Regularized Siamese Deep Network

14 0.063570261 186 nips-2011-Noise Thresholds for Spectral Clustering

15 0.062405609 265 nips-2011-Sparse recovery by thresholded non-negative least squares

16 0.058152642 172 nips-2011-Minimax Localization of Structural Information in Large Noisy Matrices

17 0.057978101 270 nips-2011-Statistical Performance of Convex Tensor Decomposition

18 0.05560397 140 nips-2011-Kernel Embeddings of Latent Tree Graphical Models

19 0.053387739 260 nips-2011-Sparse Features for PCA-Like Linear Regression

20 0.050249264 118 nips-2011-High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.119), (1, 0.027), (2, -0.039), (3, -0.11), (4, -0.078), (5, 0.07), (6, 0.021), (7, 0.101), (8, 0.112), (9, 0.057), (10, 0.097), (11, 0.021), (12, -0.058), (13, 0.014), (14, 0.07), (15, -0.138), (16, 0.025), (17, -0.037), (18, -0.058), (19, 0.01), (20, 0.032), (21, 0.033), (22, -0.028), (23, -0.16), (24, -0.011), (25, 0.037), (26, -0.108), (27, -0.026), (28, 0.047), (29, 0.034), (30, -0.036), (31, 0.072), (32, 0.052), (33, -0.11), (34, 0.078), (35, -0.157), (36, -0.063), (37, 0.047), (38, 0.04), (39, -0.194), (40, 0.029), (41, -0.002), (42, 0.074), (43, -0.025), (44, -0.072), (45, 0.065), (46, -0.012), (47, 0.056), (48, 0.063), (49, 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93850464 257 nips-2011-SpaRCS: Recovering low-rank and sparse matrices from compressive measurements

Author: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk

2 0.80888647 264 nips-2011-Sparse Recovery with Brownian Sensing

Author: Alexandra Carpentier, Odalric-ambrym Maillard, Rémi Munos

3 0.78510129 209 nips-2011-Orthogonal Matching Pursuit with Replacement

Author: Prateek Jain, Ambuj Tewari, Inderjit S. Dhillon

Abstract: In this paper, we consider the problem of compressed sensing where the goal is to recover all sparse vectors using a small number offixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator that leads to a general family of iterative algorithms. While one extreme of the family yields well known hard thresholding algorithms like ITI and HTP[17, 10], the other end of the spectrum leads to a novel algorithm that we call Orthogonal Matching Pursnit with Replacement (OMPR). OMPR, like the classic greedy algorithm OMP, adds exactly one coordinate to the support at each iteration, based on the correlation with the current residnal. However, unlike OMP, OMPR also removes one coordinate from the support. This simple change allows us to prove that OMPR has the best known guarantees for sparse recovery in terms of the Restricted Isometry Property (a condition on the measurement matrix). In contrast, OMP is known to have very weak performance guarantees under RIP. Given its simple structore, we are able to extend OMPR using locality sensitive hashing to get OMPR-Hasb, the first provably sub-linear (in dimensionality) algorithm for sparse recovery. Our proof techniques are novel and flexible enough to also permit the tightest known analysis of popular iterative algorithms such as CoSaMP and Subspace Pursnit. We provide experimental results on large problems providing recovery for vectors of size up to million dimensions. We demonstrste that for large-scale problems our proposed methods are more robust and faster than existing methods.

4 0.76620471 73 nips-2011-Divide-and-Conquer Matrix Factorization

Author: Lester W. Mackey, Michael I. Jordan, Ameet Talwalkar

Abstract: This work introduces Divide-Factor-Combine (DFC), a parallel divide-andconquer framework for noisy matrix factorization. DFC divides a large-scale matrix factorization task into smaller subproblems, solves each subproblem in parallel using an arbitrary base matrix factorization algorithm, and combines the subproblem solutions using techniques from randomized matrix approximation. Our experiments with collaborative ﬁltering, video background modeling, and simulated data demonstrate the near-linear to super-linear speed-ups attainable with this approach. Moreover, our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm.

5 0.76302594 203 nips-2011-On the accuracy of l1-filtering of signals with block-sparse structure

Author: Fatma K. Karzan, Arkadi S. Nemirovski, Boris T. Polyak, Anatoli Juditsky

6 0.73559594 297 nips-2011-Universal low-rank matrix recovery from Pauli measurements

7 0.53113806 259 nips-2011-Sparse Estimation with Structured Dictionaries

8 0.50461286 230 nips-2011-RTRMC: A Riemannian trust-region method for low-rank matrix completion

9 0.49823678 172 nips-2011-Minimax Localization of Structural Information in Large Noisy Matrices

10 0.4898718 265 nips-2011-Sparse recovery by thresholded non-negative least squares

11 0.47600606 211 nips-2011-Penalty Decomposition Methods for Rank Minimization

12 0.47194499 239 nips-2011-Robust Lasso with missing and grossly corrupted observations

13 0.4084909 5 nips-2011-A Denoising View of Matrix Completion

14 0.37292302 165 nips-2011-Matrix Completion for Multi-label Image Classification

15 0.35773158 161 nips-2011-Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation

16 0.35459346 108 nips-2011-Greedy Algorithms for Structurally Constrained High Dimensional Problems

17 0.35335279 118 nips-2011-High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity

18 0.35224631 260 nips-2011-Sparse Features for PCA-Like Linear Regression

19 0.35041612 70 nips-2011-Dimensionality Reduction Using the Sparse Linear Model

20 0.33815166 164 nips-2011-Manifold Precis: An Annealing Technique for Diverse Sampling of Manifolds

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.041), (4, 0.029), (20, 0.032), (26, 0.02), (31, 0.067), (33, 0.011), (34, 0.247), (39, 0.014), (43, 0.102), (45, 0.097), (57, 0.036), (65, 0.016), (74, 0.075), (83, 0.04), (84, 0.016), (87, 0.028), (99, 0.046)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.81394267 11 nips-2011-A Reinforcement Learning Theory for Homeostatic Regulation

Author: Mehdi Keramati, Boris S. Gutkin

Abstract: Reinforcement learning models address animal’s behavioral adaptation to its changing “external” environment, and are based on the assumption that Pavlovian, habitual and goal-directed responses seek to maximize reward acquisition. Negative-feedback models of homeostatic regulation, on the other hand, are concerned with behavioral adaptation in response to the “internal” state of the animal, and assume that animals’ behavioral objective is to minimize deviations of some key physiological variables from their hypothetical setpoints. Building upon the drive-reduction theory of reward, we propose a new analytical framework that integrates learning and regulatory systems, such that the two seemingly unrelated objectives of reward maximization and physiological-stability prove to be identical. The proposed theory shows behavioral adaptation to both internal and external states in a disciplined way. We further show that the proposed framework allows for a uniﬁed explanation of some behavioral pattern like motivational sensitivity of different associative learning mechanism, anticipatory responses, interaction among competing motivational systems, and risk aversion.

2 0.77580184 158 nips-2011-Learning unbelievable probabilities

Author: Xaq Pitkow, Yashar Ahmadian, Ken D. Miller

Abstract: Loopy belief propagation performs approximate inference on graphical models with loops. One might hope to compensate for the approximation by adjusting model parameters. Learning algorithms for this purpose have been explored previously, and the claim has been made that every set of locally consistent marginals can arise from belief propagation run on a graphical model. On the contrary, here we show that many probability distributions have marginals that cannot be reached by belief propagation using any set of model parameters or any learning algorithm. We call such marginals ‘unbelievable.’ This problem occurs whenever the Hessian of the Bethe free energy is not positive-deﬁnite at the target marginals. All learning algorithms for belief propagation necessarily fail in these cases, producing beliefs or sets of beliefs that may even be worse than the pre-learning approximation. We then show that averaging inaccurate beliefs, each obtained from belief propagation using model parameters perturbed about some learned mean values, can achieve the unbelievable marginals. 1

same-paper 3 0.74223775 257 nips-2011-SpaRCS: Recovering low-rank and sparse matrices from compressive measurements

Author: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk

4 0.67049974 140 nips-2011-Kernel Embeddings of Latent Tree Graphical Models

Author: Le Song, Eric P. Xing, Ankur P. Parikh

Abstract: Latent tree graphical models are natural tools for expressing long range and hierarchical dependencies among many variables which are common in computer vision, bioinformatics and natural language processing problems. However, existing models are largely restricted to discrete and Gaussian variables due to computational constraints; furthermore, algorithms for estimating the latent tree structure and learning the model parameters are largely restricted to heuristic local search. We present a method based on kernel embeddings of distributions for latent tree graphical models with continuous and non-Gaussian variables. Our method can recover the latent tree structures with provable guarantees and perform local-minimum free parameter learning and efﬁcient inference. Experiments on simulated and real data show the advantage of our proposed approach. 1

5 0.64315999 157 nips-2011-Learning to Search Efficiently in High Dimensions

Author: Zhen Li, Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, Thomas S. Huang

Abstract: High dimensional similarity search in large scale databases becomes an important challenge due to the advent of Internet. For such applications, specialized data structures are required to achieve computational efﬁciency. Traditional approaches relied on algorithmic constructions that are often data independent (such as Locality Sensitive Hashing) or weakly dependent (such as kd-trees, k-means trees). While supervised learning algorithms have been applied to related problems, those proposed in the literature mainly focused on learning hash codes optimized for compact embedding of the data rather than search efﬁciency. Consequently such an embedding has to be used with linear scan or another search algorithm. Hence learning to hash does not directly address the search efﬁciency issue. This paper considers a new framework that applies supervised learning to directly optimize a data structure that supports efﬁcient large scale search. Our approach takes both search quality and computational cost into consideration. Speciﬁcally, we learn a boosted search forest that is optimized using pair-wise similarity labeled examples. The output of this search forest can be efﬁciently converted into an inverted indexing data structure, which can leverage modern text search infrastructure to achieve both scalability and efﬁciency. Experimental results show that our approach signiﬁcantly outperforms the start-of-the-art learning to hash methods (such as spectral hashing), as well as state-of-the-art high dimensional search algorithms (such as LSH and k-means trees).

6 0.60329086 296 nips-2011-Uniqueness of Belief Propagation on Signed Graphs

7 0.59875292 258 nips-2011-Sparse Bayesian Multi-Task Learning

8 0.59440523 276 nips-2011-Structured sparse coding via lateral inhibition

9 0.5939256 186 nips-2011-Noise Thresholds for Spectral Clustering

10 0.58995718 183 nips-2011-Neural Reconstruction with Approximate Message Passing (NeuRAMP)

11 0.58885151 265 nips-2011-Sparse recovery by thresholded non-negative least squares

12 0.58876228 281 nips-2011-The Doubly Correlated Nonparametric Topic Model

13 0.58856881 273 nips-2011-Structural equations and divisive normalization for energy-dependent component analysis

14 0.58533567 118 nips-2011-High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity

15 0.58456993 144 nips-2011-Learning Auto-regressive Models from Sequence and Non-sequence Data

16 0.58316076 239 nips-2011-Robust Lasso with missing and grossly corrupted observations

17 0.58079916 9 nips-2011-A More Powerful Two-Sample Test in High Dimensions using Random Projection

18 0.58040619 135 nips-2011-Information Rates and Optimal Decoding in Large Neural Populations

19 0.58032387 84 nips-2011-EigenNet: A Bayesian hybrid of generative and conditional models for sparse learning

20 0.58012521 71 nips-2011-Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators