If you recall Marco mentioned the GlobalSIP 2013 Symposium on: Low-Dimensional Models and Optimization in Signal Processing. Pierre just twitted about the GlobalSIP Graph Signal Processing workshop, while Waheed twitted about New Sensing and Statistical Inference Methods clearly GlobalSIP will be the place to be in December. Submission deadline for all these workshops is June 1, 2013.
Alex Petukhov sent me the following a week ago:
Thanks Alex, I will feature those papers tomorrow!Dear Igor,I'd like to present a few sparse recovery related preprints (joint with I.Kozlov)for Nuit Blanche. One common idea behind the algorithms in all 3 preprints is a greedy envelope over the existing "basic" algorithm. Generally, this idea is extendable on many other algorithms.The first preprint is about error resilient compressed sensing. The second one is about low-rank matrix completion from corrupted and incomplete samples. The third one is about subspace clustering from corrupted, incomplete, and noisy data.The links to the preprints are here:Best regards,Alex Petukhov
I contacted Gitta Kutyniok and Marc Pfetsch about the availability of the book of abstract for the Workshop on Sparse Representation of Functions: Analytic and Computational Aspects that took place in Berlin, on December 10-14th last year. As it stands it is here. However, the pdf is not searchable and therefore invisible to the search engines. Gitta and Marc kindly sent me a searchable version (which will be posted on the site soon). In the meantime, here are the abstracts:
AbstractsCommunications Inspired Linear Discriminant AnalysisRobert CalderbankDuke University, USAWe study the problem of supervised linear dimensionality reduction, taking an informationtheoretic viewpoint. The linear projection matrix is designed by maximizing the mutual information between the projected signal and the class label. By harnessing a recent theoretical result on the gradient of mutual information, the above optimization problem can be solved directly using gradient descent, without requiring simpliﬁcation of the objective function. Theoretical analysis and empirical comparison are made between the proposed method and two closely related methods, and comparisons are also made with a method in which Renyi entropy is used to deﬁne the mutual information (in this case the gradient may be computed simply, under a special parameter setting). Relative to these alternative approaches, the proposed method achieves promising results on real datasets.
Learning non-parametric basis independent models from point queries via low-rank methodsVolkan CevherEPFL Lausanne, SwitzerlandWe consider the problem of learning multi-ridge functions of the form f(x) = g(Ax) from point evaluations of f. We assume that the function f is deﬁned on an `2-ball in Rd , g is twice continuously diﬀerentiable almost everywhere, and A 2 Rk d is a rank k matrix, where k is much greater than d. We propose a randomized, polynomial-complexity sampling scheme for estimating such functions. Our theoretical developments leverage recent techniques from low rank matrix recovery, which enables us to derive a polynomial time estimator of the function f along with uniform approximation guarantees. We prove that our scheme can also be applied for learning functions of the form: f(x) = Pk i=1 gi(a Ti x), provided f satisﬁes certain smoothnessconditions in a neighborhood around the origin. We also characterize the noise robustness of the scheme. Finally, we present numerical examples to illustrate the theoretical bounds in action.
Tensor Sparsity of Solutions to High Dimensional PDEsWolfgang DahmenRWTH Aachen, GermanyFunctions of a possibly very large number of variables arise for instance as solutions to parametric families of PDEs or of PDEs with a large number diﬀerentiable variables such as the Schrodinger equation in quantum chemistry or Fokker-Planck equations modeling dilute polymers. In this talk we discuss the (near) tensor sparsity of solutions to certain high dimensional diﬀusion equations resulting from operator splitting applied to Fokker-Planck equations. We report on results obtained jointly with L. Grasedyck, E. Süli, and partly with R. DeVore concerning the question: given (nearly) tensor sparse data for such equations, are the solutions (nearly) tensor sparse and if so, how can this be quantiﬁed?
TBAIngrid DaubechiesDuke University, USA
Sparse Stabilization and Optimal Control of the Cucker and Smale SystemMassimo FornasierTU München, GermanyFrom a mathematical point of view self-organization can be described as steady patterns, to which certain dynamical systems modeling social dynamics tend autonomously to be attracted. In this talk we explore situations beyond self-organization, in particular how to externally control such dynamical systems in order to eventually enforce pattern formation also in those situations where this wished phenomenon does not result from spontaneous and autonomous convergence. Our focus is on dynamical systems of Cucker-Smale type, modeling consensus emergence, and we question the existence of stabilization and optimal control strategies which require the minimal amount of external intervention for nevertheless inducing consensus in a group of interacting agents. In mathematical terms, our main result realizes the connection between certain variational problems involving `1-norm terms and optimally sparse controls. Our ﬁndings can also be informally stated in terms of the general principle for which a policy maker should always consider more favorable to intervene with stronger actions on the fewest possible instantaneous optimal leaders than try to control more agents with minor strength, in order to achieve group consensus.
Sparse Representation in Hierarchical Tensor FormatsLars GrasedyckRWTH Aachen, GermanyThe (numerical) linear algebra related to tensor computations plays an immensely powerful role in theoretical and applied sciences: applied mathematics, biology, chemistry, information sciences, physics and many other areas. In this talk we consider high-order or high-dimensional tensors, respectively functions, of the formA 2 R n n; f : [0;1]d ! R as they appear in multivariate (discrete or continuous) approximation problems. These require special techniques in order to allow a representation and approximation for high dimension d (cf. the curse of dimension). A typical example is the canonical polyadic (CP) format Ai1;:::;id =Xrj=1Yd =1a ;j(i ); f(x1; : : : ; xd) = Xrj=1Yd =1f ;j(x ) with discrete, respectively continuous, functions a ;j : f1; : : : ; ng ! R; f ;j : [0;1] ! R that require O(d n r) degrees of freedom or the representation of dr one-dimensional functions f ;j. However, this simple format comes along with several numerical obstructions, because it is highly non-linear.In the last four years some new hierarchical formats (namely Tensor Train and Hierarchical Tucker) have been developed and analysed. These include as a subset all tensors of CP format (rank parameter r ﬁxed), but in addition they allow for some nice linear algebra approaches, e.g. a hierarchical SVD in complexity O(d n r 2 +d r4). The hierarchical SVD is similar to the SVD for matrices in the sense that it allows us to reliably compute a quasi-best approximation in the hierarchical format. We will outline the basic linear algebra behind the new approaches as well as open questions and possible applications. In particular, we will consider a standard two- or three-dimensionalSparse dictionary learning in the presence of noise & outliersRémi GribonvalProjet METISS, IRISA, Rennes, FranceA popular approach within the signal processing and machine learning communities consists in modelling signals as sparse linear combinations of atoms selected from a learned dictionary. While this paradigm has led to numerous empirical successes in various ﬁelds ranging from image to audio processing, there have only been a few theoretical arguments supporting these evidences. In particular, sparse coding, or sparse dictionary learning, relies on a non-convex procedure whose local minima have not been fully analyzed yet. Considering a probabilistic model of sparse signals, we show that, with high probability, sparse coding admits a local minimum around the reference dictionary generating the signals. Our study takes into account the case of over-complete dictionaries and noisy signals, thus extending previous work limited to noiseless settings and/or under-complete dictionaries. The analysis we conduct is non-asymptotic and makes it possible to understand how the key quantities of the problem, such as the coherence or the level of noise, can scale with respect to the dimension of the signals, the number of atoms, the sparsity and the number of observations. Joint work with Rodolphe Jenatton & Francis Bach
Breaking the Coherence Barrier: Semi-random Sampling in Compressed SensingAnders HansenUniversity of Cambridge, United KingdomIt is well known that compressed sensing relies on two crucial assumptions: incoherence and sparsity. Although there are examples where one has both of these features, there are surprisingly many cases in applications where these criteria are not satisﬁed. In particular, Fourier sampling and wavelet or polynomial reconstruction (both essential in Magnetic Resonance Imaging (MRI)). To overcome this obstacle we introduce a new theory where the assumptions of incoherence and sparsity are replaced by two new features: asymptotic incoherence and asymptotic sparsity. These two ideas combined with diﬀerent semi-random sampling schemes allow for dramatic subsampling in cases that previously were limited by the lack of incoherence/sparsity.Moreover, we demonstrate that asymptotic incoherence and asymptotic sparsity + semi-random sampling yield a rather intriguing eﬀect: higher resolution allows for substantially better subsampling than with lower resolution. In particular, this new technique is excellent for high resolution problems.Joint work with Ben Adcock
Low-rank tensor completion by Riemannian optimizationDaniel KressnerEPFL LausanneThe aim of tensor completion is to ﬁll in missing entries of a partially known tensor under a low-rank constraint. We propose a new algorithm that performs Riemannian optimization techniques on the manifolds of tensors of ﬁxed multilinear rank. More speciﬁcally, a variant of the nonlinear conjugate gradient method is developed. Particular attention is paid to the eﬃcient computation of the diﬀerent ingredients, including the gradient, retraction and vector transport. Examples with synthetic data demonstrate good recovery even if the vast majority of the entries is unknown. Finally, we illustrate the use of the developed algorithm for the approximation of functions with singularities.Joint work with Michael Steinlechner (EPFL) and Bart Vanderecken (U Princeton)
Clustered Sparsity and Separation of Cartoon and TextureGitta KutyniokTU Berlin, GermanyNatural images are typically a composition of cartoon and texture structures. A medical image might, for instance, show a mixture of gray matter and the skull cap. One common task is to separate such an image into two single images, one containing the cartoon part and the other containing the texture part. Using compressed sensing techniques, numerous inspiring empirical results have already been obtained.In this paper we provide the ﬁrst thorough theoretical study of the separation of a combination of cartoon and texture structures in a model situation. The methodology we consider expands the image in a combined dictionary consisting of a shearlet tight frame and a Gabor tight frame and minimizes the `1 norm on the analysis side. Sparse approximation properties then force the cartoon components into the shearlet coeﬃcients and the texture components into the Gabor coeﬃcients, thereby separating the image. Utilizing the fact that the coeﬃcients are clustered geometrically and endowing a Gabor system with a scale, we prove that at suﬃciently ﬁne scalesarbitrarily precise separation is possible.
Sparse dual framesJakob LemvigTU Danmark, DanmarkFrames are generalizations of bases which lead to redundant signal expansions, and they play an important role in many applications, e.g., in the theory of nonuniform sampling, wireless communications, and Sigma-Delta quantization. Sparsity of frame vectors (in some ﬁxed orthonormal basis) is a new paradigm in frame theory that among other things allows for simple representation of the frame vectors and fast analysis and reconstruction procedures. Recently, a general construction method for sparse tight frames was considered in [Casazza, Heinecke, Krahmer, Kutyniok, Optimally sparse frames, IEEE Trans. IT]. In this talk, we study sparse dual frames of a given (not necessarily tight nor sparse) frame. We characterize the optimal sparsity level in the set of all duals and present numerical algorithms for ﬁnding sparse dual with desirable properties.Joint work with Felix Krahmer and Gitta KutyniokComputational Solver Comparison for Basis PursuitMarc PfetschTU Darmstadt, GermanyThe problem of ﬁnding a minimum `1-norm solution to an underdetermined linear system (basis pursuit) is undoubtedly one of the central problems in compressed sensing. Many specialized solution approaches have been proposed and (matlab) implementations are available. This talks presents an extensive numerical comparison of seven such solvers and discusses the benchmarking methodology. Moreover, we propose a heuristic optimality check (HOC) as a general tool for l_1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an approximate support.Joint work with Dirk Lorenz and Andreas Tillmann
Scalable FramesFriedrich PhilippTU Berlin, GermanyTight frames can be characterized as those frames which possess optimal numerical stability properties. Here, we consider the question of modifying a general frame to generate a tight frame by simply scaling its frame vectors; a process which can also be regarded as perfect preconditioning of a frame by a diagonal matrix. A frame is called scalable, if such a diagonal matrix exists. We derive various characterizations of scalable frames and provide a geometrical interpretation of scalability in terms of conical surfaces. Finally, it is shown that – loosely speaking – the set of scalable frames is thin in the set of frames.
Function interpolation via weighted `1-minimizationHolger RauhutUniversity of Bonn, GermanyWe consider the problem of interpolating a function from sample values. Building on insights from compressive sensing, we study weighted `1-minimization as recovery/interpolation method. Assuming that the function to be recovered has a sparse expansion in terms of the Fourier system or more general orthonormal systems including orthogonal polynomials, compressive sensing predicts that the function can be recovered from few samples at randomly chosen locations via (unweighted) `1-minimization. In practice, however, strict sparsity occurs rarely and has to be replaced with approximate sparsity. While also this setup is already well-understood, we takea step further and take into consideration that functions often possess a certain smoothness. Hence, low-order Fourier coeﬃcients are more likely to appear in the best s-term approximation than high-order Fourier coeﬃcients. Taking this observation into account, we use weighted lp norms with p 1 on the Fourier coeﬃcients in order to model the functions to be reconstructed. The corresponding natural recovery method turns out to be weighted l1-minimization. We will present theoretical results and promising numerical experiments. This approach is able to overcome certain limitations in the context of recovering spherical harmonic expansions. If time permits also connections to numerically solving parametric (stochastic) partial diﬀerential equations will be discussed.Joint work with Rachel Ward
High accuracy ﬁnite frame quantization using Sigma-Delta schemesRayan SaabDuke University, USAIn this talk, we address the digitization of oversampled signals in the ﬁnite-dimensional setting. In particular, we show that by quantizing the N-dimensional frame coeﬃcients of signals in Rd using Sigma-Delta quantization schemes, it is possible to achieve root- exponential accuracy in the oversampling rate := N=d (even when one bit per measurement is used). These are currently the best known error rates in this context. In particular, such error rates holds for an “optimal” family of frames (the Sobolev self-dual frames), as well as to the well-known Harmonic frames, and surprisingly to random frames from appropriate distributions. We also discuss connections and applications to quantization of compressed sensing measurements as well as open problems.Joint work with F. Krahmer, R. Ward, and O. Yilmaz
BPdual: Another Solver for BP, BPDN, NNLS, and MoreMichael SaundersStanford University, USAMany imaging and compressed sensing applications seek sparse solutions to under-determined least-squares problems. The basis pursuit (BP) approach minimizes the 1-norm of the solution, and BP denoising (BPDN) balances it against the least-squares ﬁt. The duals of these problems are conventional linear and quadratic programs. We introduce the following parameterization of the BPDN problem and its dual:min x; y kxk1 +12 kyk22 Ax + y = b;maxybTy 12 kyk22e ATy e;where e is a vectors of 1s. Exploring the eﬀectiveness of active-set methods for solving the BPDN dual led us to the generalized problems BP : min x; y c(x) Tx + 12 kyk22Ax + y = b; QP : max y bTy 12 kyk22l ATy u;wherecj(x) = (`j if xj 0,uj if xj gt 0. Our algorithm for solving QP uniﬁes several existing algorithms and is applicable to large-scale examples.Joint work with Michael Friedlander
Tensor completion and tensor recovery in recent tensor formatsReinhold SchneiderTU Berlin, GermanyHierarchical Tucker tensor format (Hackbusch) and a particular case Tensor Trains (TT) (Tyrtyshnikov) have been introduced recently oﬀering stable and robust approximation by a low order cost, and generalizing the well established Tucker format.Branch & Cut for L0-MinimizationAndreas TillmannTU Darmstadt, GermanyWhile there are many heuristics for ﬁnding a sparse solution to an underdetermined linear equation system, hardly any exact solution methods are known beside the trivial total enumeration procedure. Since ﬁnding the sparsest solution, i.e., minimizing the `0-quasinorm of a vector x satisfying Ax = b, is NP-hard, there is little hope of devising a polynomial-time solution algorithm. In this talk, we discuss work in progress on a novel Branch & Cut scheme for `0-minimization.
Random Sampling in Numerical Linear AlgebraSivan ToledoUniversity Tel Aviv, IsraelThe talk will focus on random sampling in numerical linear algebra. Traditionally, algorithms in numerical linear algebra strive for accuracy (small residual errors), which straightforward random-sampling methods do not always deliver. The talk will explain how the accuracy of randomly-sampled approximations can be improved using residual-correction methods, such as LSQR. The talk will describe cases where we do have an appropriate residual correction method and cases where we do not have such methods. We will discuss both mixing-based (random projection) methods, which are appropriate for dense problems, and leverage-scorebased methods, which are appropriate for sparse problems.
Hammersley and Fibonacci QMC beat Sparse GridsTino UllrichHausdorﬀ-Center for Mathematics/Institute for Numerical Simulation, Bonn, GermanyWe constructively prove new asymptotically optimal error bounds for numerical integration in bivariate periodic Besov spaces with dominating mixed smoothness S rp;qB(T2 ) where 1 p; q 1 and r gt 1=p. Our ﬁrst result uses Quasi-Monte Carlo integration on Fibonacci lattice rules and improves on the so far best known upper bound achieved by using cubature formula taking function values from a Sparse Grid. It is well known that there is no proper counterpart for Fibonacci lattice rules in higher dimensions. To this end, our second result is based on Hammersley (or Van der Corput) type point grids. Instead of exploiting a Hlawka-Zaremba type discrepancy duality, which is limited to 1=p lt r 1, we extend Hinrichs’ recent results to larger orders r, namely 1=p lt r lt 2. This direct approach is strongly conjectured to have aproper counterpart for higher orders r and, in addition, for functions on the d-torus Td. Last, but not least, we prove that any cubature rule based an a sparse grid in d dimensions has a signiﬁcantly worse error order than the previously described methods. These results are a ﬁrst step to understand the problem of optimal recovery of functions from a discrete set of function values from a completely new direction.
Nuclear norm optimization in system identiﬁcationLieven VandenbergheUCLA, USAThe nuclear norm (sum of singular values) of a matrix plays an important role in extensions of 1-norm techniques for sparse optimization to optimization problems involving matrix rank minimization. It has been used successfully for applications in machine learning, signal and image processing, and statistics. Formulations based on the nuclear norm penalty are also increasingly used in dynamical system identiﬁcation, as an alternative to the singular value decomposition commonly used for low-rank matrix approximations in subspace identiﬁcation algorithms. The nuclear norm approach is attractive for several reasons. It preserves linear structure (such as block Hankel structure) in the low-rank matrix approximation, additional constraints or regularization terms are easily included in the formulation, and missing measurement data can behandled in a straightforward manner. In the talk we will discuss several system identiﬁcation algorithms based on the nuclear norm penalty, as well as ﬁrst-order algorithms for solving the resulting convex optimization problems.
Algorithms and complexity for nonnegative matrix factorizationSteve VavasisUniversity of Waterloo, CanadaNonnegative matrix factorization (NMF) is a tool for approximating a large nonnegative matrix with much smaller nonnegative sparse factors. Its power stems from its ability to automatically ﬁnd features in the large matrix. It is widely used in machine learning applications including classifying text, ﬁnding features in images, interpreting the results of bioarray experiments, and even analysis of musical compositions. Recently several results have emerged concerning the theoretical complexity of NMF: it is NP-hard in general, but some interesting special cases are solvable in polynomial time. Convex relaxation in particular has proven to be a powerful solution method. Guaranteed polynomial-time algorithms and corresponding complexity bounds are a very promising line of attack in understanding NMF.Parts of this talk represent joint work with N. Gillis, X. V. Doan and K.-C. Toh.
Learning Functions of Few Arbitrary Linear Parameters in High DimensionsJan VybiralTU Berlin, GermanyWe study the uniform approximation of functions of many variables with the following inner structure. We assume, that f(x) = g(Ax), where x 2 Rd , A is a k d matrix and g is a (smooth) function on Rk . Both g and A are unknown and their recovery is a part of the problem. Under certain smoothness and variation assumptions on the function g, and an arbitrary choice of the matrix A, we present a sampling choice of the points drawn at random for each function approximation and algorithms for computing the approximating function. Due to the arbitrariness of A, the choice of the sampling points will be according to suitable random distributions and our results hold with overwhelming probability. Our approach uses tools taken from the compressed sensing framework, recent Chernoﬀ bounds for sums of positive-semideﬁnite matrices, and classical stability bounds for invariant subspaces of singular value decompositions.
Symbology-based Algorithms for Robust Bar Code RecoveryRachel WardUniversity of Texas, USAUPC bar codes can be characterized as sparse representations with respect to a certain symbology basis. We exploit this low-dimensional structure and introduce a greedy bar code reconstruction algorithm which can recover UPC bar codes from very noisy measurements and inaccurate parameter information. Extensions to general bar codes, radio-frequency identiﬁcation, and text denoising will be discussed
This image was taken by Rear Hazcam: Right B (RHAZ_RIGHT_B) onboard NASA's Mars rover Curiosity on Sol 235 (2013-04-04 10:54:53 UTC).