nips nips2008 nips2008-215 knowledge-graph by maker-knowledge-mining

215 nips-2008-Sparse Signal Recovery Using Markov Random Fields

Source: pdf

Author: Volkan Cevher, Marco F. Duarte, Chinmay Hegde, Richard Baraniuk

Abstract: Compressive Sensing (CS) combines sampling and compression into a single subNyquist linear measurement process for sparse and compressible signals. In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefﬁcients are clustered. Our new model-based recovery algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Compressive Sensing (CS) combines sampling and compression into a single subNyquist linear measurement process for sparse and compressible signals. [sent-7, score-0.296]

2 In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. [sent-8, score-0.178]

3 In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefﬁcients are clustered. [sent-9, score-0.224]

4 Our new model-based recovery algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms. [sent-10, score-0.583]

5 1 Introduction The Shannon/Nyquist sampling theorem tells us that in order to preserve information when uniformly sampling a signal we must sample at least two times faster than its bandwidth. [sent-11, score-0.231]

6 A transform compression system reduces the effective dimensionality of an N -dimensional signal by re-representing it in terms of a sparse expansion in some basis (for example, the discrete cosine transform for JPEG). [sent-14, score-0.36]

7 The new theory of compressive sensing (CS) combines sampling and compression into a single subNyquist linear measurement process for sparse signals [1, 2]. [sent-16, score-0.519]

8 In CS, we measure not periodic signal samples but rather inner products with M < N known measurement vectors; random measurement vectors play a starring role. [sent-17, score-0.381]

9 We then recover the signal by searching for the sparsest signal that agrees with the measurements. [sent-18, score-0.517]

10 Research in CS to date has focused on reducing both the number of measurements M (as a function of N and K) and on reducing the computational complexity of the recovery algorithm. [sent-19, score-0.431]

11 Today’s state-of-the-art CS systems can recover K-sparse and more general compressible signals using M = O(K log(N/K)) measurements using polynomial-time linear programming or greedy algorithms. [sent-20, score-0.382]

12 In virtually all such algorithms, the key ingredient is a signal model that goes beyond simple sparsity by providing a model for the basis coefﬁcient structure. [sent-22, score-0.306]

13 1 In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model [3]. [sent-26, score-0.178]

14 We use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefﬁcients also cluster together. [sent-27, score-0.224]

15 Our new model-based recovery algorithm, dubbed Lattice Matching Pursuit (LaMP), performs rapid and numerically stable recovery of MRF-modeled signals using far fewer measurements than standard algorithms. [sent-28, score-0.899]

16 2 Compressive sensing: From sparsity to structured sparsity Sparse signal recovery. [sent-33, score-0.404]

17 Any signal x ∈ RN can be represented in terms of N coefﬁcients {αi } in a basis {ψ i }N ; stacking the ψ i as columns into the matrix ΨN ×N , we can write succinctly i=1 that x = Ψθ. [sent-34, score-0.252]

18 We say that x has a sparse representation if only K ≪ N entries of θ are nonzero, N and we denote by ΩK the set of K possible supports for such K-sparse signals. [sent-35, score-0.139]

19 In Compressive Sensing (CS), the signal is not acquired by measuring x or α directly. [sent-37, score-0.26]

20 (1) The recovery of the set of signiﬁcant coefﬁcients θi is achieved using optimization: we search for the sparsest θ that agrees with the measurements y. [sent-42, score-0.486]

21 While in principle recovery is possible using a matrix that has the 2K-RIP with δ2K < 1, such an optimization is combinatorially complex (NPcomplete) and numerically unstable. [sent-43, score-0.308]

22 If we instead use a matrix that has the 3K-RIP with δ3K < 1/2, then numerically stable recovery is possible in polynomial time using either a linear program [1, 2] or a greedy algorithm [4]. [sent-44, score-0.371]

23 While many natural and manmade signals and images can be described to the ﬁrst-order as sparse or compressible, their sparse supports (set of nonzero coefﬁcients) often have an underlying order. [sent-47, score-0.408]

24 The theme of this paper is that by exploiting a priori information on coefﬁcient structure in addition to signal sparsity, we can make CS better, stronger, and faster. [sent-49, score-0.231]

25 Figure 1 illustrates a real-world example of structured sparse support in a computer vision application. [sent-50, score-0.163]

26 Figure 1(b) is a background subtracted image computed from a video sequence of a parking lot with two moving people (one image frame is shown in Figure 1(a)). [sent-51, score-0.333]

27 The background subtraction was computed from CS measurements of the video sequence. [sent-53, score-0.321]

28 Background subtracted images play a fundamental role in making inferences about objects and activities in a scene and, by nature, they have structured spatial sparsity corresponding to the foreground innovations. [sent-54, score-0.272]

29 In other words, compared to the scale of the scene, the foreground innovations are usually not only sparse but also clustered in a distinct way, e. [sent-55, score-0.151]

30 Nevertheless, this clustering property is not exploited by current CS recovery algorithms. [sent-58, score-0.261]

31 However, if we incorporate a probabilistic model on our signal supports and consider only the signal supports with the highest likelihoods, then we can potentially do much better in terms of the required number of measurements required for stable recovery. [sent-61, score-0.814]

32 We say that Φ satisﬁes the (K, ǫ)-probabilistic RIP (PRIP) if there exists a constant δK > 0 such that for a K-sparse signal x generated by a speciﬁed probabilistic signal model, (1) holds with probability at least 1 − ǫ over the signal probability space. [sent-62, score-0.716]

33 We propose a preliminary result on the 2 PSfrag (a) (b) (c) Figure 1: A camera surveillance image (b) with the background subtracted image (b) recovered using compressive measurements of the scene. [sent-63, score-0.636]

34 The background subtracted image has resolution N = 240 × 320 and sparsity K = 390. [sent-64, score-0.291]

35 (c) A random K = 390 sparse image in N = 240 × 320 dimensions. [sent-65, score-0.158]

36 The probability of image (b) under the Ising model is approximately 10856 times greater than the probability of image (c). [sent-66, score-0.168]

37 number of random measurements needed under this new criterion; this is a direct consequence of Theorem 5. [sent-67, score-0.17]

38 Suppose that M , N , and δ ∈ [0, 1] are given and that the signal x is generated by a known probabilistic model. [sent-71, score-0.254]

39 Let ΩK,ǫ ⊆ ΩK denote the smallest set of supports for which the probability that a K-sparse signal x has supp(x) ∈ ΩK,ǫ is less than ǫ, and denote D = |ΩK,ǫ |. [sent-72, score-0.296]

40 We determine the size of the likely K-sparse support set ΩK under this particular signal model using a simple counting argument. [sent-80, score-0.297]

41 When α is on the order of (log N )−1 , the number of measurements required and the complexity of the solution method grow essentially linearly in K, which is a considerable improvement over the best possible M = O(K log(N/K)) measurements required without such a priori information. [sent-86, score-0.34]

42 3 Graphical models for compressive sensing Clustering of the nonzero coefﬁcients in a sparse signal representation can be realistically captured by a probabilistic graphical model such as a Markov random ﬁeld (MRF); in this paper we will focus for concreteness on the classical Ising model [10]. [sent-87, score-0.676]

43 We begin with an Ising model for the signal support. [sent-89, score-0.231]

44 Suppose we have a K-sparse signal x ∈ RN whose support is represented by s ∈ {−1, 1}N such that si = −1 when xi = 0 and si = 1 when xi = 0. [sent-90, score-0.817]

45 The probability density function (PDF) of the signal support can be modeled using a graph Gs = (Vs , Es ), where Vs = {1, . [sent-91, score-0.32]

46 , N } denotes a set of N vertices – one for each of the support indices – and Es denotes the set of edges connecting support indices that are spatial neighbors (see Figure 2(a)). [sent-94, score-0.18]

47 The contribution of the interaction between two elements {si , sj } in the support of x is controlled by the coefﬁcient λij > 0. [sent-95, score-0.156]

48 signal support s and consists of the edge interaction parameters λij and the vertex bias parameters λi . [sent-98, score-0.297]

49 For example, compare the clustered sparsity of the real background subtracted image in Figure 1(b) with the dispersed “independent” sparsity of the random image in Figure 1(c). [sent-101, score-0.488]

50 45 and λi = 0), the image (b) is approximately 10856 times more likely than the image (c). [sent-103, score-0.168]

51 Under this model, the support is controlled by an Ising model, and the signal values are independent given the support. [sent-107, score-0.317]

52 We now develop a joint PDF for the image pixel values x, the support labels s, and the CS measurements y. [sent-108, score-0.32]

53 We assume that the measurements y are corrupted by i. [sent-111, score-0.17]

54 From Figure 2(c), it is easy to show that, given the signal x, the signal support s and the compressive measurements y are independent using the D-separation property of graphs [13]. [sent-117, score-0.864]

55 Then, (3) can be explicitly written as p(z) ∝ exp    λij si sj + (i,j)∈Es [λi si + log(p(xi |si ))] − i∈Vs   1 ||y − Φx||2 . [sent-119, score-0.484]

56 2  2σ 2 (4) 4 Lattice matching pursuit Using the coefﬁcient graphical model from Section 3, we are now equipped to develop a new modelbased CS signal recovery algorithm. [sent-120, score-0.693]

57 Lattice Matching Pursuit (LaMP) is a greedy algorithm for signals on 2D lattices (images) in which the likelihood of the signal support is iteratively evaluated and optimized under an Ising model. [sent-121, score-0.417]

58 Similar to other greedy recovery algorithms such as matching pursuit and CoSaMP [4], each iteration of LaMP starts by estimating a data residual r {k} given the current estimate of the signal x{k−1} (Step 1). [sent-125, score-0.675]

59 After calculating the {k} residual, LaMP calculates a temporary signal estimate (Step 2) denoted by xt . [sent-126, score-0.313]

60 This signal esti′ {k} mate is the sum of the previous estimate x{k−1} and Φ r , accounting for the current residual. [sent-127, score-0.231]

61 Using this temporary signal estimate as a starting point, LaMP then maximizes the likelihood (4) over the support via optimization (Step 3). [sent-128, score-0.356]

62 Propose a temporary target signal estimate: {k} xt = Φ′ r {k} + x{k−1} ; Step 3. [sent-133, score-0.313]

63 Determine MAP estimate of the support using graph cuts: {k} s{k} = maxs∈{−1,+1}N (i,j)∈Es λij si sj + i∈Vs λi si + log(p([xt ]i |si )) ; Step 4. [sent-134, score-0.573]

64 Once a likely signal support s{k} is obtained in Step 3, LaMP obtains an updated signal estimate x{k} using least squares with the selected columns of the measurement matrix Φ[:, s{k} = 1] and pruning back to the largest K signal coefﬁcients (Step 4). [sent-140, score-0.875]

65 If the graphical model includes dependencies between the signal values xi , we then replace the pseudoinverse product by a belief propagation algorithm to efﬁciently solve for the signal values x{k} within Step 4. [sent-143, score-0.57]

66 The correct signal PDF to use given the support p(x|s) is problem-dependent. [sent-145, score-0.297]

67 Here, we provide one approximation that mimics the ℓ0 minimization for CS recovery for the signal graphical model in Figure 2(c); we also use this in our experiments in Section 5. [sent-146, score-0.571]

68 The state si = 1 represents a nonzero coefﬁcient; thus, all nonzero values of xi should have equal probability, and the value xi = 0 should have zero probability. [sent-147, score-0.441]

69 Similarly, the state si = −1 represents a zero-valued coefﬁcient; thus, the mass of its probability function is concentrated at zero. [sent-148, score-0.207]

70 However, the optimization over the joint PDF in (4) requires a “smoothing” of these PDFs for two reasons: (i) to obtain robustness against noise and numerical issues; and (ii) to extend the usage of the algorithm from sparse to compressible signals. [sent-150, score-0.24]

71 Here, the constant τ is a slack parameter to separate large and small signal coefﬁcients, and ǫ1 , ǫ2 , and ǫ3 are chosen according to τ and L to normalize each PDF. [sent-152, score-0.231]

72 Using the normalization constraints, it is possible to show that as the dynamic range increases, lim − L→∞ 1 log ǫ2 → and log ǫ1 τa 5 lim − L→∞ log ǫ3 → 0. [sent-154, score-0.168]

73 max s∈{−1,+1}N {k+1} λij si sj + λi si + Usi ([xt ]i ; τ ) , (5) i∈Vs (i,j)∈Es If the signal values are known to be positive, then the deﬁnitions of Usi can be changed to enforce the positivity during estimation. [sent-157, score-0.715]

74 To enforce a desired sparsity K on the lattice structure, we apply statistical mechanics results on 1 the 2D Ising model and choose λij = 0. [sent-159, score-0.198]

75 In our recovery problem, the average magnetization and the desired signal sparsity has a simple relationship: m = (+1) × K + (−1) × (N − K) /N . [sent-161, score-0.59]

76 We set λi = 0 unless there is prior information on the signal support. [sent-162, score-0.231]

77 We obtained compressive measurements of this image, which were then immersed in additive white Gaussian noise to an SNR of 10dB. [sent-169, score-0.373]

78 The top row of Figure 4 illustrates the iterative image estimates obtained using LaMP from just M = 2K = 3480 random Gaussian measurements of the noisy target. [sent-170, score-0.254]

79 Within 3 iterations, the support of the image is accurately determined; convergence occurs at the 5th iteration. [sent-171, score-0.15]

80 Figure 4 (bottom) compares LaMP to CoSaMP [4], a state-of-the-art greedy recovery algorithm, and ﬁxed-point continuation (FPC) [17], a state-of-the-art ℓ1 -norm minimization recovery algorithm using the same set of measurements. [sent-172, score-0.608]

81 Despite the presence of high noise (10dB SNR), LaMP perfectly recovers the signal support from only a small number of measurements. [sent-173, score-0.334]

82 We tested both LaMP and FPC with a number of measurements that gave close to perfect recovery of the Shepp-Logan phantom in the presence of a small amount of noise; for LaMP, setting M = 1. [sent-177, score-0.475]

83 We then studied the degradation of the recovery quality as a function of the noise level for both algorithms. [sent-179, score-0.298]

84 The results in Figure 5(a) demonstrate that LaMP is stable for a wide range of measurement noise levels. [sent-181, score-0.141]

85 Indeed, the rate of increase of the LaMP recovery error as a function of the noise variance σ (a measure of the stability to noise) is comparable to that of FPC, while using far fewer measurements. [sent-182, score-0.356]

86 We test the recovery algorithms over a set of background subtraction images. [sent-184, score-0.379]

87 The images were obtained from a test video sequence, one image frame of which is shown in Figure 1, by choosing at random two frames from the video and subtracting them in a pixel-wise fashion. [sent-185, score-0.195]

88 We created 100 different test images; for each image, we deﬁne the sparsity K as the number of coefﬁcients 1 We use the GCOptimization package [14–16] to solve the support recovery problem in Step 3 in Algorithm 1 in our implementation of LaMP. [sent-187, score-0.402]

89 5s Figure 4: Top: LaMP recovery of the Shepp-Logan phantom (N = 100 × 100, K = 1740, SNR = 10dB) Maximum reconstruction error 3000 2500 Average normalized error magnitude from M = 2K = 3480 noisy measurements. [sent-196, score-0.305]

90 (a) Maximum recovery error over 1000 noise iterations as a function of the input noise variance. [sent-202, score-0.335]

91 We then performed recovery of the image using the LaMP, CoSaMP, and FPC algorithms under varying number of measurements M , from 0. [sent-208, score-0.515]

92 LaMP’s graphical model reduces the number of measurements necessary for acceptable recovery quality to M ≈ 2. [sent-213, score-0.486]

93 5K, while the standard algorithms require M ≥ 5K measurements to achieve the same quality. [sent-214, score-0.17]

94 6 Conclusions We have presented an initial study of model-based CS signal recovery using an MRF model to capture the structure of the signal’s sparse coefﬁcients. [sent-215, score-0.566]

95 As demonstrated in our numerical simulations, for signals conforming to our model, the resulting LaMP algorithm requires signiﬁcantly fewer CS measurements, has lower computational complexity, and has equivalent numerical stability to the current state-of-the-art algorithms. [sent-216, score-0.218]

96 We are working to precisely quantify the reduction in the required number of measurements (our numerical experiments suggest that M = O(K) is sufﬁcient for stable recovery) and computations. [sent-219, score-0.236]

97 We also assert that probabilistic signal models hold the key to formulating inference problems in the compressive measurement domain since in many signal processing applications, signals are acquired merely for the purpose of making an inference such as a detection or classiﬁcation decision. [sent-220, score-0.841]

98 7 Target LaMP CoSaMP FPC Figure 6: Example recoveries for background subtraction images, using M = 3K for each image. [sent-221, score-0.155]

99 CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. [sent-247, score-0.492]

100 Wavelet-domain compressive signal reconstruction using a hidden Markov tree model. [sent-266, score-0.397]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('lamp', 0.582), ('recovery', 0.261), ('cs', 0.244), ('signal', 0.231), ('fpc', 0.226), ('si', 0.207), ('cosamp', 0.185), ('measurements', 0.17), ('compressive', 0.166), ('ising', 0.15), ('coef', 0.128), ('pdf', 0.111), ('lattice', 0.1), ('compressible', 0.092), ('pursuit', 0.086), ('signals', 0.086), ('image', 0.084), ('cients', 0.082), ('rice', 0.081), ('sparsity', 0.075), ('measurement', 0.075), ('duarte', 0.074), ('sparse', 0.074), ('sj', 0.07), ('subtracted', 0.069), ('support', 0.066), ('supports', 0.065), ('nonzero', 0.064), ('background', 0.063), ('sensing', 0.063), ('mrf', 0.059), ('temporary', 0.059), ('log', 0.056), ('rip', 0.055), ('usi', 0.055), ('subtraction', 0.055), ('compression', 0.055), ('graphical', 0.055), ('xi', 0.053), ('vs', 0.053), ('ij', 0.049), ('images', 0.045), ('baraniuk', 0.044), ('phantom', 0.044), ('jpeg', 0.044), ('matching', 0.04), ('foreground', 0.039), ('clustered', 0.038), ('numerical', 0.037), ('cevher', 0.037), ('chinmay', 0.037), ('concisely', 0.037), ('prip', 0.037), ('recoveries', 0.037), ('sankaranarayanan', 0.037), ('subnyquist', 0.037), ('volkan', 0.037), ('noise', 0.037), ('fewer', 0.034), ('greedy', 0.034), ('snr', 0.033), ('magnitudes', 0.033), ('video', 0.033), ('compress', 0.032), ('dubbed', 0.032), ('likelihoods', 0.032), ('sparsest', 0.03), ('acquired', 0.029), ('cuts', 0.029), ('stable', 0.029), ('step', 0.028), ('fields', 0.028), ('yin', 0.028), ('continuation', 0.028), ('isometry', 0.028), ('boykov', 0.028), ('numerically', 0.026), ('markov', 0.025), ('mrfs', 0.025), ('zs', 0.025), ('agrees', 0.025), ('stability', 0.024), ('indices', 0.024), ('minimization', 0.024), ('xt', 0.023), ('location', 0.023), ('structured', 0.023), ('residual', 0.023), ('probabilistic', 0.023), ('locations', 0.023), ('graph', 0.023), ('desired', 0.023), ('enforcing', 0.022), ('scene', 0.021), ('matrix', 0.021), ('es', 0.021), ('controlled', 0.02), ('pruning', 0.02), ('equipped', 0.02), ('enforces', 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 215 nips-2008-Sparse Signal Recovery Using Markov Random Fields

Author: Volkan Cevher, Marco F. Duarte, Chinmay Hegde, Richard Baraniuk

2 0.16021216 207 nips-2008-Shape-Based Object Localization for Descriptive Classification

Author: Geremy Heitz, Gal Elidan, Benjamin Packer, Daphne Koller

Abstract: Discriminative tasks, including object categorization and detection, are central components of high-level computer vision. Sometimes, however, we are interested in more reﬁned aspects of the object in an image, such as pose or particular regions. In this paper we develop a method (LOOPS) for learning a shape and image feature model that can be trained on a particular object class, and used to outline instances of the class in novel images. Furthermore, while the training data consists of uncorresponded outlines, the resulting LOOPS model contains a set of landmark points that appear consistently across instances, and can be accurately localized in an image. Our model achieves state-of-the-art results in precisely outlining objects that exhibit large deformations and articulations in cluttered natural images. These localizations can then be used to address a range of tasks, including descriptive classiﬁcation, search, and clustering. 1

3 0.14663361 179 nips-2008-Phase transitions for high-dimensional joint support recovery

Author: Sahand Negahban, Martin J. Wainwright

Abstract: Given a collection of r ≥ 2 linear regression problems in p dimensions, suppose that the regression coefﬁcients share partially common supports. This set-up suggests the use of 1 / ∞ -regularized regression for joint estimation of the p × r matrix of regression coefﬁcients. We analyze the high-dimensional scaling of 1 / ∞ -regularized quadratic programming, considering both consistency rates in ∞ -norm, and also how the minimal sample size n required for performing variable selection grows as a function of the model dimension, sparsity, and overlap between the supports. We begin by establishing bounds on the ∞ error as well sufﬁcient conditions for exact variable selection for ﬁxed design matrices, as well as designs drawn randomly from general Gaussian matrices. These results show that the high-dimensional scaling of 1 / ∞ -regularization is qualitatively similar to that of ordinary 1 -regularization. Our second set of results applies to design matrices drawn from standard Gaussian ensembles, for which we provide a sharp set of necessary and sufﬁcient conditions: the 1 / ∞ -regularized method undergoes a phase transition characterized by the rescaled sample size θ1,∞ (n, p, s, α) = n/{(4 − 3α)s log(p − (2 − α) s)}. More precisely, for any δ > 0, the probability of successfully recovering both supports converges to 1 for scalings such that θ1,∞ ≥ 1 + δ, and converges to 0 for scalings for which θ1,∞ ≤ 1 − δ. An implication of this threshold is that use of 1,∞ -regularization yields improved statistical efﬁciency if the overlap parameter is large enough (α > 2/3), but performs worse than a naive Lasso-based approach for moderate to small overlap (α < 2/3). We illustrate the close agreement between these theoretical predictions, and the actual behavior in simulations. 1

4 0.13956702 198 nips-2008-Resolution Limits of Sparse Coding in High Dimensions

Author: Sundeep Rangan, Vivek Goyal, Alyson K. Fletcher

Abstract: This paper addresses the problem of sparsity pattern detection for unknown ksparse n-dimensional signals observed through m noisy, random linear measurements. Sparsity pattern recovery arises in a number of settings including statistical model selection, pattern detection, and image acquisition. The main results in this paper are necessary and sufﬁcient conditions for asymptotically-reliable sparsity pattern recovery in terms of the dimensions m, n and k as well as the signal-tonoise ratio (SNR) and the minimum-to-average ratio (MAR) of the nonzero entries of the signal. We show that m > 2k log(n − k)/(SNR · MAR) is necessary for any algorithm to succeed, regardless of complexity; this matches a previous sufﬁcient condition for maximum likelihood estimation within a constant factor under certain scalings of k, SNR and MAR with n. We also show a sufﬁcient condition for a computationally-trivial thresholding algorithm that is larger than the previous expression by only a factor of 4(1 + SNR) and larger than the requirement for lasso by only a factor of 4/MAR. This provides insight on the precise value and limitations of convex programming-based algorithms.

5 0.13597497 21 nips-2008-An Homotopy Algorithm for the Lasso with Online Observations

Author: Pierre Garrigues, Laurent E. Ghaoui

Abstract: It has been shown that the problem of 1 -penalized least-square regression commonly referred to as the Lasso or Basis Pursuit DeNoising leads to solutions that are sparse and therefore achieves model selection. We propose in this paper RecLasso, an algorithm to solve the Lasso with online (sequential) observations. We introduce an optimization problem that allows us to compute an homotopy from the current solution to the solution after observing a new data point. We compare our method to Lars and Coordinate Descent, and present an application to compressive sensing with sequential observations. Our approach can easily be extended to compute an homotopy from the current solution to the solution that corresponds to removing a data point, which leads to an efﬁcient algorithm for leave-one-out cross-validation. We also propose an algorithm to automatically update the regularization parameter after observing a new data point. 1

6 0.12703064 166 nips-2008-On the asymptotic equivalence between differential Hebbian and temporal difference learning using a local third factor

7 0.11235752 201 nips-2008-Robust Near-Isometric Matching via Structured Learning of Graphical Models

8 0.1061428 106 nips-2008-Inferring rankings under constrained sensing

9 0.098426759 99 nips-2008-High-dimensional support union recovery in multivariate regression

10 0.097896509 135 nips-2008-Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of \boldmath$\ell 1$-regularized MLE

11 0.095874041 69 nips-2008-Efficient Exact Inference in Planar Ising Models

12 0.0947726 226 nips-2008-Supervised Dictionary Learning

13 0.089140229 238 nips-2008-Theory of matching pursuit

14 0.082147159 62 nips-2008-Differentiable Sparse Coding

15 0.078982361 30 nips-2008-Bayesian Experimental Design of Magnetic Resonance Imaging Sequences

16 0.071827054 75 nips-2008-Estimating vector fields using sparse basis field expansions

17 0.066410884 2 nips-2008-A Convex Upper Bound on the Log-Partition Function for Binary Distributions

18 0.06387271 74 nips-2008-Estimating the Location and Orientation of Complex, Correlated Neural Activity using MEG

19 0.062784284 118 nips-2008-Learning Transformational Invariants from Natural Movies

20 0.062638752 148 nips-2008-Natural Image Denoising with Convolutional Networks

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.195), (1, -0.037), (2, 0.001), (3, 0.047), (4, 0.127), (5, 0.009), (6, -0.147), (7, -0.098), (8, -0.006), (9, 0.042), (10, -0.151), (11, -0.106), (12, 0.006), (13, -0.016), (14, -0.053), (15, -0.012), (16, 0.115), (17, 0.037), (18, 0.076), (19, -0.008), (20, 0.122), (21, -0.062), (22, -0.076), (23, 0.018), (24, 0.006), (25, 0.125), (26, -0.136), (27, -0.068), (28, 0.04), (29, -0.046), (30, -0.029), (31, -0.045), (32, 0.035), (33, -0.117), (34, 0.063), (35, 0.183), (36, 0.126), (37, -0.006), (38, -0.088), (39, 0.033), (40, 0.026), (41, -0.13), (42, -0.022), (43, 0.16), (44, 0.024), (45, -0.054), (46, -0.159), (47, 0.029), (48, 0.028), (49, 0.076)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94460535 215 nips-2008-Sparse Signal Recovery Using Markov Random Fields

Author: Volkan Cevher, Marco F. Duarte, Chinmay Hegde, Richard Baraniuk

2 0.56026566 106 nips-2008-Inferring rankings under constrained sensing

Author: Srikanth Jagabathula, Devavrat Shah

Abstract: Motivated by applications like elections, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings using constrained data. More speciﬁcally, we consider the problem of inferring a probability distribution over the group of permutations using its ﬁrst order marginals. We ﬁrst prove that it is not possible to recover more than O(n) permutations over n elements with the given information. We then provide a simple and novel algorithm that can recover up to O(n) permutations under a natural stochastic model; in this sense, the algorithm is optimal. In certain applications, the interest is in recovering only the most popular (or mode) ranking. As a second result, we provide an algorithm based on the Fourier Transform over the symmetric group to recover the mode under a natural majority condition; the algorithm turns out to be a maximum weight matching on an appropriately deﬁned weighted bipartite graph. The questions considered are also thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing. 1

3 0.55906397 201 nips-2008-Robust Near-Isometric Matching via Structured Learning of Graphical Models

Author: Alex J. Smola, Julian J. Mcauley, Tibério S. Caetano

Abstract: Models for near-rigid shape matching are typically based on distance-related features, in order to infer matches that are consistent with the isometric assumption. However, real shapes from image datasets, even when expected to be related by “almost isometric” transformations, are actually subject not only to noise but also, to some limited degree, to variations in appearance and scale. In this paper, we introduce a graphical model that parameterises appearance, distance, and angle features and we learn all of the involved parameters via structured prediction. The outcome is a model for near-rigid shape matching which is robust in the sense that it is able to capture the possibly limited but still important scale and appearance variations. Our experimental results reveal substantial improvements upon recent successful models, while maintaining similar running times. 1

4 0.50435466 198 nips-2008-Resolution Limits of Sparse Coding in High Dimensions

Author: Sundeep Rangan, Vivek Goyal, Alyson K. Fletcher

5 0.46725678 166 nips-2008-On the asymptotic equivalence between differential Hebbian and temporal difference learning using a local third factor

Author: Christoph Kolodziejski, Bernd Porr, Minija Tamosiunaite, Florentin Wörgötter

Abstract: In this theoretical contribution we provide mathematical proof that two of the most important classes of network learning - correlation-based differential Hebbian learning and reward-based temporal difference learning - are asymptotically equivalent when timing the learning with a local modulatory signal. This opens the opportunity to consistently reformulate most of the abstract reinforcement learning framework from a correlation based perspective that is more closely related to the biophysics of neurons. 1

6 0.46397614 207 nips-2008-Shape-Based Object Localization for Descriptive Classification

7 0.43833584 75 nips-2008-Estimating vector fields using sparse basis field expansions

8 0.42761633 30 nips-2008-Bayesian Experimental Design of Magnetic Resonance Imaging Sequences

9 0.42258456 2 nips-2008-A Convex Upper Bound on the Log-Partition Function for Binary Distributions

10 0.41048098 179 nips-2008-Phase transitions for high-dimensional joint support recovery

11 0.40839463 21 nips-2008-An Homotopy Algorithm for the Lasso with Online Observations

12 0.39511496 226 nips-2008-Supervised Dictionary Learning

13 0.38853678 69 nips-2008-Efficient Exact Inference in Planar Ising Models

14 0.37017456 238 nips-2008-Theory of matching pursuit

15 0.36437112 74 nips-2008-Estimating the Location and Orientation of Complex, Correlated Neural Activity using MEG

16 0.34843919 99 nips-2008-High-dimensional support union recovery in multivariate regression

17 0.3477073 149 nips-2008-Near-minimax recursive density estimation on the binary hypercube

18 0.34463143 135 nips-2008-Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of \boldmath$\ell 1$-regularized MLE

19 0.33310539 157 nips-2008-Nonrigid Structure from Motion in Trajectory Space

20 0.31078961 62 nips-2008-Differentiable Sparse Coding

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(6, 0.077), (7, 0.067), (12, 0.035), (15, 0.018), (24, 0.011), (25, 0.013), (28, 0.124), (53, 0.013), (57, 0.074), (59, 0.048), (63, 0.012), (71, 0.013), (77, 0.071), (78, 0.01), (83, 0.053), (94, 0.282)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.75918603 136 nips-2008-Model selection and velocity estimation using novel priors for motion patterns

Author: Shuang Wu, Hongjing Lu, Alan L. Yuille

Abstract: Psychophysical experiments show that humans are better at perceiving rotation and expansion than translation. These ﬁndings are inconsistent with standard models of motion integration which predict best performance for translation [6]. To explain this discrepancy, our theory formulates motion perception at two levels of inference: we ﬁrst perform model selection between the competing models (e.g. translation, rotation, and expansion) and then estimate the velocity using the selected model. We deﬁne novel prior models for smooth rotation and expansion using techniques similar to those in the slow-and-smooth model [17] (e.g. Green functions of differential operators). The theory gives good agreement with the trends observed in human experiments. 1

same-paper 2 0.74068487 215 nips-2008-Sparse Signal Recovery Using Markov Random Fields

Author: Volkan Cevher, Marco F. Duarte, Chinmay Hegde, Richard Baraniuk

3 0.69638586 60 nips-2008-Designing neurophysiology experiments to optimally constrain receptive field models along parametric submanifolds

Author: Jeremy Lewi, Robert Butera, David M. Schneider, Sarah Woolley, Liam Paninski

Abstract: Sequential optimal design methods hold great promise for improving the efﬁciency of neurophysiology experiments. However, previous methods for optimal experimental design have incorporated only weak prior information about the underlying neural system (e.g., the sparseness or smoothness of the receptive ﬁeld). Here we describe how to use stronger prior information, in the form of parametric models of the receptive ﬁeld, in order to construct optimal stimuli and further improve the efﬁciency of our experiments. For example, if we believe that the receptive ﬁeld is well-approximated by a Gabor function, then our method constructs stimuli that optimally constrain the Gabor parameters (orientation, spatial frequency, etc.) using as few experimental trials as possible. More generally, we may believe a priori that the receptive ﬁeld lies near a known sub-manifold of the full parameter space; in this case, our method chooses stimuli in order to reduce the uncertainty along the tangent space of this sub-manifold as rapidly as possible. Applications to simulated and real data indicate that these methods may in many cases improve the experimental efﬁciency. 1

4 0.68791461 17 nips-2008-Algorithms for Infinitely Many-Armed Bandits

Author: Yizao Wang, Jean-yves Audibert, Rémi Munos

Abstract: We consider multi-armed bandit problems where the number of arms is larger than the possible number of experiments. We make a stochastic assumption on the mean-reward of a new selected arm which characterizes its probability of being a near-optimal arm. Our assumption is weaker than in previous works. We describe algorithms based on upper-conﬁdence-bounds applied to a restricted set of randomly selected arms and provide upper-bounds on the resulting expected regret. We also derive a lower-bound which matches (up to a logarithmic factor) the upper-bound in some cases. 1

5 0.55510002 216 nips-2008-Sparse probabilistic projections

Author: Cédric Archambeau, Francis R. Bach

Abstract: We present a generative model for performing sparse probabilistic projections, which includes sparse principal component analysis and sparse canonical correlation analysis as special cases. Sparsity is enforced by means of automatic relevance determination or by imposing appropriate prior distributions, such as generalised hyperbolic distributions. We derive a variational Expectation-Maximisation algorithm for the estimation of the hyperparameters and show that our novel probabilistic approach compares favourably to existing techniques. We illustrate how the proposed method can be applied in the context of cryptoanalysis as a preprocessing tool for the construction of template attacks. 1

6 0.55120385 79 nips-2008-Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

7 0.55008954 75 nips-2008-Estimating vector fields using sparse basis field expansions

8 0.55006272 62 nips-2008-Differentiable Sparse Coding

9 0.54841435 179 nips-2008-Phase transitions for high-dimensional joint support recovery

10 0.54748535 245 nips-2008-Unlabeled data: Now it helps, now it doesn't

11 0.54690427 202 nips-2008-Robust Regression and Lasso

12 0.54612875 194 nips-2008-Regularized Learning with Networks of Features

13 0.54518819 116 nips-2008-Learning Hybrid Models for Image Annotation with Partially Labeled Data

14 0.54384899 200 nips-2008-Robust Kernel Principal Component Analysis

15 0.54356176 63 nips-2008-Dimensionality Reduction for Data in Multiple Feature Representations

16 0.54303318 230 nips-2008-Temporal Difference Based Actor Critic Learning - Convergence and Neural Implementation

17 0.54303038 205 nips-2008-Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization

18 0.54230881 21 nips-2008-An Homotopy Algorithm for the Lasso with Online Observations

19 0.54147702 27 nips-2008-Artificial Olfactory Brain for Mixture Identification

20 0.54005975 226 nips-2008-Supervised Dictionary Learning