Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
We present a multiscale based method that accelerates the Particle Filter computation. Particle Filter is a powerful method that tracks the state of a target based on non-linear observations. Unlike the conventional way that calculates weights over all particles in each cycle of the algorithm, we sample a small subset from the source particles using matrix decomposition methods. Then, we apply a function extension algorithm that uses the particle subset to recover the density function for all the rest of the particles. As often happens, the computational effort is substantial especially when tracking multiple objects takes place. The proposed algorithm reduces significantly the computational load. By using the Fast Gaussian Transform, the particle selection step changes from O(k2n log n) operations to O(n + k log n) operations where n is the number of particles and k the selected subset size. We demonstrate our method on both simulated and on real data such as tracking in videos sequences.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
The performance of sparse signal recovery can be improved if both sparsity and correlation structure of signals can be exploited. One typical correlation structure is intra-block correlation in block sparse signals. To exploit this structure, a framework, called block sparse Bayesian learning (BSBL) framework, has been proposed recently. Algorithms derived from this framework showed promising performance but their speed is not very fast, which limits their applications. This work derives an efficient algorithm from this framework, using a marginalized likelihood maximization method. Thus it can exploit block sparsity and intra-block correlation of signals. Compared to existing BSBL algorithms, it has close recovery performance to them, but has much faster speed. Therefore, it is more suitable for recovering large scale datasets.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.A new workstation designed for Compressive Sensing researchersInView Technology Corporation, the world leader in Compressive Sensing (CS) imaging products, has launched the first in a series of CS Workstations. The InView220 provides CS researchers with the ability to easily prototype and test novel CS algorithms on a complete hardware imaging platform. Researchers are provided with unprecedented ability to apply novel measurement bases to a high-speed, high-definition spatial light modulator, and to process the light levels measured from Shortwave Infrared (SWIR) detectors.The major components of the InView220 are an imaging Sensor, which includes a 1920x1080 digital micromirror device and a 32-diode detector array, and a Sensor Controller, which is preloaded with the InView Development Environment (IDE) software
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Dear Colleague,
It is our pleasure to announce that in September 30 -- October 11, 2013 the Les Houches center for theoretical physics will be hosting an autumn school "Statistical physics, Optimization, Inference and Message-Passing algorithms" organized by Florent Krzakala, Federico Ricci-Tersenghi, Lenka Zdeborova and Riccardo Zecchnia.The aim of this two-weeks school is to teach in a widely accessible manner about Statistical physics, Optimization, Inference and Message-Passing algorithms. Lectures will be given both by physicists and by researchers from computer science, machine learning and signal processing. The goal is to present methods and applications from several different angles and help the participants to cross bridges between different disciplines. The school is aimed not only for PhD students, postdocs but also for confirmed researchers who wish to understand better the presented topics. More information and a list of confirmed lecturers can be found on the workshop website:All students and researchers wishing to participate should apply on the website by April 30, 2013. According to the number of applicants they will be informed in June about subsequent steps.Please forward the link to the website to all students, postdocs and researcher that might be interested.With best regards and looking forward to see many of you next October in Les HouchesThe organizers
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Hello Igor,
.....
The reason I'm writing to you is regarding a sparse modeling software that I just released. The package is called COSMOS and is currently in its alpha version.The interesting thing about it, which is the core of my PhD, [Thesis: Second Generation Sparse Models ] is that it works with automatic model selection criteria, so that things such as desired sparsity in the solutions, or dictionary sizes, are automatically chosen based on, for example, information theoretic principles such as MDL, AIC or BIC.It also contains some interesting variants on traditional dictionary learning methods, such as bounded and total variation based atom learning.Please check it out at http://iie.fing.edu.uy/~nacho/cosmos/I have other stuff that may be of interest to your blog. Please visit http://iie.fing.edu.uy/~nacho (especially the Software and Publications sections) to see them.Regards,
Ignacio.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin."Once you're living in the future in some respect, the way to notice startup ideas is to look for things that seem to be missing. If you're really at the leading edge of a rapidly changing field, there will be things that are obviously missing. What won't be obvious is that they're startup ideas. So if you want to find startup ideas, don't merely turn on the filter "What's missing?" Also turn off every other filter, particularly "Could this be a big company?" There's plenty of time to apply that test later. But if you're thinking about that initially, it may not only filter out lots of good ideas, but also cause you to focus on bad ones."
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Evidently, this promise comes with the caveat that message-passing algorithms are specifically designed to solve sparse-recovery problems for Gaussian matrices while methods such as SPGL1 are versatile and solve BP for any A and b as long one is willing to spend a sufficient number of iterations to bring the residual down.
We consider the recovery of sparse signals from a limited number of noisy observations using the AMP algorithm. In this paper, we present two fast implementations of this algorithm that run on a CPU and on a GPU and which can either be used for arbitrary unstructured measurement matrices or take advantage of the structure of a DCT matrix to give an even faster implementation. Our results show that for small problem sizes, the CPU based implementation is the fastest, but for large problem sizes, a GPU based implementation has the highest throughput.
Sparse signal recovery finds use in a variety of practical applications, such as signal and image restoration and the recovery of signals acquired by compressive sensing. In this paper, we present two generic VLSI architectures that implement the approximate message passing (AMP) algorithm for sparse signal recovery. The first architecture, referred to as AMP-M, employs parallel multiply-accumulate units and is suitable for recovery problems based on unstructured (e.g., random) matrices. The second architecture, referred to as AMP-T, takes advantage of fast linear transforms, which arise in many real-world applications. To demonstrate the effectiveness of both architectures, we present corresponding VLSI and FPGA implementation results for an audio restoration application. We show that AMP-T is superior to AMP-M with respect to silicon area, throughput, and power consumption, whereas AMP-M offers more flexibility.
To meet current-day challenges, exploration seismology increasingly relies on more and more sophisticated algorithms that require multiple paths through all data. This requirement leads to problems because the size of seismic data volumes is increasing exponentially, exposing bottlenecks in IO and computational capability. To overcome these bottlenecks, we follow recent trends in machine learning and compressive sensing by proposing a sparsity-promoting inversion technique that works on small randomized subsets of data only. We boost the performance of this algorithm significantly by modifying a state-of-the-art `1-norm solver to benefit from message passing, which breaks the build up of correlations between model iterates and the randomized linear forward model. We demonstrate the performance of this algorithm on a toy sparse-recovery problem and on a realistic reverse-time-migration example with random source encoding. The improvements in speed, memory use, and output quality are truly remarkable.
Data collection, data processing, and imaging in exploration seismology increasingly hinge on large-scale sparsity promoting solvers to remove artifacts caused by efforts to reduce costs. We show how the inclusion of a “message term“ in the calculation of the residuals improves the convergence of these iterative solvers by breaking correlations that develop between the model iterate and the linear system that needs to be inverted. We compare this message-passing scheme to state-of-the-art solvers for problems in missing-trace interpolation and in dimensionality-reduced imaging with phase encoding.
In this paper, we apply compressed sensing to video compression. Compressed sensing (CS) techniques exploit the observation that one needs much fewer random measurements than given by the Shannon-Nyquist sampling theory to recover an object if this object is compressible (i.e., sparse in the spatial domain or in a transform domain). In the CS framework, we can achieve sensing, compression and denoising simultaneously. We propose a fast and simple online encoding by application of pseudo-random downsampling of the two-dimensional fast Fourier transform to video frames. For off-line decoding, we apply a modification of the recently proposed approximate message passing (AMP) algorithm. The AMP method has been derived using the statistical concept of ’state evolution’, and it has been shown to considerably accelerate the convergence rate in special CS-decoding applications. We shall prove that the AMP method can be rewritten as a forward-backward splitting algorithm. This new representation enables us to give conditions that ensure convergence of the AMP method and to modify the algorithm in order to achieve higher robustness. The success of reconstruction methods for video decoding also essentially depends on the chosen transform, where sparsity of the video signals is assumed. We propose to incorporate the 3D dual-tree complex wavelet transform that possesses sufficiently good properties of directional selectivity and shift invariance while being computationally less expensive and less redundant than other directional 3D wavelet transforms.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Functional neuroimaging can measure the brain’s response to an external stimulus. It is used to perform brain mapping: identifying from these observations the brain regions involved. This problem can be cast into a linear supervised learning task where the neuroimaging data are used as predictors for the stimulus. Brain mapping is then seen as a support recovery problem. On functional MRI (fMRI) data, this problem is particularly challenging as i) the number of samples is small due to limited acquisition time and ii) the variables are strongly correlated. We propose to overcome these difficulties using sparse regression models over new variables obtained by clustering of the original variables. The use of randomization techniques, e.g. bootstrap samples, and hierarchical clustering of the variables improves the recovery properties of sparse methods. We demonstrate the benefit of our approach on an extensive simulation study as well as two publicly available fMRI datasets.
The scattering transform is a hierarchical signal transformation that has been designed to be robust to signal deformations. It can be used to compute representations with invariance or tolerance to any transformation group, such as translations, rotations or scaling. In image analysis, going beyond edge detection, its second layer captures higher order features, providing a fine-grain dissection of the signal. Here we use the output coefficients to fit blood oxygen level dependent (BOLD) signal in visual areas using functional magnetic resonance imag- ing. Significant improvement in the prediction accuracy is shown when using the second layer in addition to the first, suggesting biological relevance of the features extracted in layer two or linear combinations thereof.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
This work studies the recursive robust principal components' analysis(PCA) problem. Here, "robust" refers to robustness to both independent and correlated sparse outliers. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low dimensional subspace that is either fixed or changes "slowly enough". A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above problem, we introduce a novel solution called Recursive Projected CS (ReProCS). Under mild assumptions, we show that, with high probability (w.h.p.), ReProCS can exactly recover the support set of St at all times; and the reconstruction errors of both St and Lt are upper bounded by a time-invariant and small value at all times. We also show how the algorithm and its guarantees extend to the undersampled measurements' case.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Abstract. Regularization plays a key role in a variety of optimization formulations of inverse problems. A recurring question in regularization approaches is the selection of regularization pa- rameters, and its e ect on the solution and on the optimal value of the optimization problem. The sensitivity of the value function to the regularization parameter can be linked directly to the Lagrange multipliers. In this paper, we fully characterize the variational properties of the value functions for a broad class of convex formulations, which are not all covered by standard Lagrange multiplier theory. We also present an inverse function theorem that links the value functions of di erent regularization formulations (not necessarily convex). These results have implications for the selection of regularization parameters, and the development of specialized algorithms. We give numerical examples that illustrate the theoretical results.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Fast Earth Mover's Distance (EMD) Code
(C++ and Matlab and Java wrappers)
The code efficiently computes the Earth Mover's Distance (EMD) between two histograms or sparse histograms (signatures). The EMD is also known as Mallows, 1st Wasserstein, Monge-Kantorovich, Match and Transporatation distances. The approach was described in the paper:
"Fast and Robust Earth Mover's Distances" [,
].
EMD-HAT (a better definition of EMD for non-normalized histograms) was presented in the paper:
"A Linear Time Histogram Metric for Improved SIFT Matching" [
One of the demos (demo_FastEMD4) includes a C++ implementation of the CIEDE2000 color distance. The CIEDE2000 C++ code is an adaption of Prof. Gaurav Sharma's Matlab code (used with permission). Other demos include comparison of David Lowe's SIFT descriptors, simple 1d histogram comparison and grayscale image comparison.
Quadratic Chi (QC) - code that computes the new Quadratic Chi histogram distances (proposed at ECCV 2010) very fast.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Usual information theoretical results show a logarithmic compression factor of value spaces to digital binary spaces using p-adic numbering systems. The following paper discusses a less commonly used case. It applies the same results to the difference space of bijective mappings of $n$-dimensional spaces to the line. It discusses a method where the logarithmic compression factor is provided over the Hamming radius of the code. An example is provided using the 35GB data dump of the Wikipedia website. This technique was initially developed for the study and computation of large permutation vectors on small clusters.
An archetypal problem discussed in computer science is the problem of searching for a given number in a given set of numbers. Other than sequential search, the classic solution is to sort the list of numbers and then apply binary search. The binary search problem has a complexity of O(logN) for a list of N numbers while the sorting problem cannot be better than O(N) on any sequential computer following the usual assumptions. Whenever the problem of deciding partial order can be done in O(1), a variation of the problem on some bounded list of numbers is to apply binary search without resorting to sort. The overall complexity of the problem is then O(log R) for some radius R. A logarithmic upper-bound for finite encodings is shown. Also, the topology of orderings can provide efficient algorithms for search problems in combinatorial spaces. The main characteristic of those spaces is that they have typical exponential space complexities. The factorial case describes an order topology that can be illustrated using the combinatorial polytope . When a known order topology can be combined to a given formulation of a search problem, the resulting search problem has a polylogarithmic complexity. This logarithmic complexity can then become useful in combinatorial search by providing a logarithmic break-down. These algorithms can be termed as the class of search algorithms that do not require read and are equivalent to the class of logarithmically recursive functions.
At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore theBig Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization andcalibration issues on Linkedin.
