In sparse recovery we are given a matrix @math (the dictionary) and a vector of the form @math where @math is sparse, and the goal is to recover @math . This is a central notion in signal processing, statistics and machine learning. But in applications such as sparse coding, edge detection, compression and super resolution, the dictionary @math is unknown and has to be learned from random examples of the form @math where @math is drawn from an appropriate distribution --- this is the dictionary learning problem. In most settings, @math is overcomplete: it has more columns than rows. This paper presents a polynomial-time algorithm for learning overcomplete dictionaries; the only previously known algorithm with provable guarantees is the recent work of Spielman, Wang and Wright who gave an algorithm for the full-rank case, which is rarely the case in applications. Our algorithm applies to incoherent dictionaries which have been a central object of study since they were introduced in seminal work of Donoho and Huo. In particular, a dictionary is @math -incoherent if each pair of columns has inner product at most @math . The algorithm makes natural stochastic assumptions about the unknown sparse vector @math , which can contain @math non-zero entries (for any @math ). This is close to the best @math allowable by the best sparse recovery algorithms even if one knows the dictionary @math exactly. Moreover, both the running time and sample complexity depend on @math , where @math is the target accuracy, and so our algorithms converge very quickly to the true dictionary. Our algorithm can also tolerate substantial amounts of noise provided it is incoherent with respect to the dictionary (e.g., Gaussian). In the noisy setting, our running time and sample complexity depend polynomially on @math , and this is necessary.
When the entries of @math are independent, algorithms for independent component analysis or ICA can recover @math . @cite_12 gave a provable algorithm that recovers @math up to arbitrary accuracy, provided entries in @math are non-Gaussian (when @math is Gaussian, @math is only determined up to rotations anyway). Subsequent works considered the overcomplete case and gave provable algorithms even when @math is @math with @math .
@cite_12
2147544992 2160634130 2568310503 2119385818
Comon's (1994) well-known scheme for independent component analysis (ICA) is based on the maximal diagonalization, in a least-squares sense, of a higher-order cumulant tensor. In a previous paper, we proved that for fourth-order cumulants, the computation of an elementary Jacobi rotation is equivalent to the computation of the best rank-1 approximation of a fourth-order tensor. In this paper, we show that for third-order tensors, the computation of an elementary Jacobi rotation is again equivalent to a best rank-1 approximation; however, here, it is a matrix that has to be approximated. This favorable computational load makes it attractive to do "something third-order-like" for fourth-order cumulant tensors as well. We show that simultaneous optimal diagonalization of "third-order tensor slices" of the fourth-order cumulant is a suitable strategy. This "simultaneous third-order tensor diagonalization" approach (STOTD) is similar in spirit to the efficient JADE-algorithm. An algorithm based on independent component analysis (ICA) is introduced for P300 detection. After ICA decomposition, P300-related independent components are selected according to the a priori knowledge of P300 spatio-temporal pattern, and clear P300 peak is reconstructed by back projection of ICA. Applied to the dataset IIb of BCI Competition 2003, the algorithm achieved an accuracy of 100 in P300 detection within five repetitions. The notion of recoverable value was advocated in the work of Feige, Immorlica, Mirrokni and Nazerzadeh (APPROX 2009) as a measure of quality for approximation algorithms. There, this concept was applied to facility location problems. In the current work we apply a similar framework to the maximum independent set problem (MIS). We say that an approximation algorithm has recoverable factor ρ, if for every graph it recovers an independent set of size at least where d(v) is the degree of vertex v, and I ranges over all independent sets in G. Hence, in a sense, from every vertex v in the maximum independent set the algorithm recovers a value of at least toward the solution. This quality measure is most effective in graphs in which the maximum independent set is composed of low degree vertices. A simple greedy algorithm achieves . We design a new randomized algorithm for MIS that ensures an expected recoverable factor of at least . In passing, we prove that approximating MIS in graphs with a given k-coloring within a ratio larger than 2 k is unique-games hard. This rules out an alternative approach for obtaining . © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 142–159, 2015 In sparse recovery we are given a matrix @math (the dictionary) and a vector of the form @math where @math is sparse, and the goal is to recover @math . This is a central notion in signal processing, statistics and machine learning. But in applications such as sparse coding, edge detection, compression and super resolution, the dictionary @math is unknown and has to be learned from random examples of the form @math where @math is drawn from an appropriate distribution --- this is the dictionary learning problem. In most settings, @math is overcomplete: it has more columns than rows. This paper presents a polynomial-time algorithm for learning overcomplete dictionaries; the only previously known algorithm with provable guarantees is the recent work of Spielman, Wang and Wright who gave an algorithm for the full-rank case, which is rarely the case in applications. Our algorithm applies to incoherent dictionaries which have been a central object of study since they were introduced in seminal work of Donoho and Huo. In particular, a dictionary is @math -incoherent if each pair of columns has inner product at most @math . The algorithm makes natural stochastic assumptions about the unknown sparse vector @math , which can contain @math non-zero entries (for any @math ). This is close to the best @math allowable by the best sparse recovery algorithms even if one knows the dictionary @math exactly. Moreover, both the running time and sample complexity depend on @math , where @math is the target accuracy, and so our algorithms converge very quickly to the true dictionary. Our algorithm can also tolerate substantial amounts of noise provided it is incoherent with respect to the dictionary (e.g., Gaussian). In the noisy setting, our running time and sample complexity depend polynomially on @math , and this is necessary.