SPORCO: Convolutional Dictionary Learning - implementation -

Brendt sent me the following a few days ago: 

Hi Igor,
We have two new papers on convolutional dictionary learning as well as some recent related code. Could you please post an announcement on Nuit Blanche?
Brendt

Sure Brendt ! It is already mentioned in the Advanced Matrix Factorization Jungle Page as this is an awesome update to the previous announcement.

"Convolutional Dictionary Learning: A Comparative Review and New Algorithms", available from http://dx.doi.org/10.1109/TCI.2018.2840334 and https://arxiv.org/abs/1709.02893, reviews existing batch-mode convolutional dictionary learning algorithms and proposes some new ones with significantly improved performance. Implementations of all of the most competitive algorithms are included in the Python version of the SPORCO library at https://github.com/bwohlberg/sporco .

"First and Second Order Methods for Online Convolutional Dictionary Learning", available from http://dx.doi.org/10.1137/17M1145689 and https://arxiv.org/abs/1709.00106, extends our previous work and proposes some new algorithms for online convolutional dictionary learning that we believe outperform existing alternatives. Implementations of all of the new algorithms are included in the

Matlab version of the SPORCO library at http://purl.org/brendt/software/sporco and the first order algorithm is also included in the Python version of the SPORCO library at https://github.com/bwohlberg/sporco . A very recent addition to the Python version is the ability to exploit the SPORCO-CUDA extension to greatly accelerate the learning process.

Convolutional Dictionary Learning: A Comparative Review and New Algorithms by Cristina Garcia-Cardona, Brendt Wohlberg

Convolutional sparse representations are a form of sparse representation with a dictionary that has a structure that is equivalent to convolution with a set of linear filters. While effective algorithms have recently been developed for the convolutional sparse coding problem, the corresponding dictionary learning problem is substantially more challenging. Furthermore, although a number of different approaches have been proposed, the absence of thorough comparisons between them makes it difficult to determine which of them represents the current state of the art. The present work both addresses this deficiency and proposes some new approaches that outperform existing ones in certain contexts. A thorough set of performance comparisons indicates a very wide range of performance differences among the existing and proposed methods, and clearly identifies those that are the most effective.

First and Second Order Methods for Online Convolutional Dictionary Learning by Jialin Liu, Cristina Garcia-Cardona, Brendt Wohlberg, Wotao Yin

Convolutional sparse representations are a form of sparse representation with a structured, translation invariant dictionary. Most convolutional dictionary learning algorithms to date operate in batch mode, requiring simultaneous access to all training images during the learning process, which results in very high memory usage and severely limits the training data that can be used. Very recently, however, a number of authors have considered the design of online convolutional dictionary learning algorithms that offer far better scaling of memory and computational cost with training set size than batch methods. This paper extends our prior work, improving a number of aspects of our previous algorithm; proposing an entirely new one, with better performance, and that supports the inclusion of a spatial mask for learning from incomplete data; and providing a rigorous theoretical analysis of these methods.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
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.

SPORCO: A Python package for standard and convolutional sparse representations - implementation -

Brendt just sent me the following:

Hi Igor,
I noticed that you maintain an extensive list of software tools for sparse representations and related problems. Could you please add a reference to SPORCO, which is a relatively new library providing algorithms for sparse coding and dictionary learning? It supports standard sparse representations as well as a variety of other problems, including ℓ1-TV and ℓ2-TV regularization and Robust PCA, but the major strength is in algorithms for convolutional sparse coding and dictionary learning (the form of sparse coding inspired by deconvolutional networks). 

A Matlab version is available at 

http://purl.org/brendt/software/sporco 

but development is now focused on the Python version, available on GitHub at

https://github.com/bwohlberg/sporco 

The Python version features an object-oriented design that allows the existing ADMM algorithms to be extended or modified with limited effort, as described in some detail in paper presented at the recent SciPy conference 

http://conference.scipy.org/proceedings/scipy2017/brendt_wohlberg.html

Thanks,
Brendt

Thanks Brendt ! Let me add this to the Advanced Matrix Factorization Jungle page in the coming days. In the meantime, here is the paper:  

SPORCO: A Python package for standard and convolutional sparse representations by Brendt Wohlberg

SParse Optimization Research COde (SPORCO) is an open-source Python package for solving optimization problems with sparsity-inducing regularization, consisting primarily of sparse coding and dictionary learning, for both standard and convolutional forms of sparse representation. In the current version, all optimization problems are solved within the Alternating Direction Method of Multipliers (ADMM) framework. SPORCO was developed for applications in signal and image processing, but is also expected to be useful for problems in computer vision, statistics, and machine learning.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
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.

Random Feature Expansions for Deep Gaussian Processes / AutoGP: Exploring the Capabilities and Limitations of Gaussian Process Models - implementation -

[I will be at ICLR next week, let's grab some coffee if you are there]

Random Feature Expansions for Deep Gaussian Processes by Kurt Cutajar, Edwin V. Bonilla, Pietro Michiardi, Maurizio Filippone

The composition of multiple Gaussian Processes as a Deep Gaussian Process (DGP) enables a deep probabilistic nonparametric approach to flexibly tackle complex machine learning problems with sound quantification of uncertainty. Existing inference approaches for DGP models have limited scalability and are notoriously cumbersome to construct. In this work, we introduce a novel formulation of DGPs based on random feature expansions that we train using stochastic variational inference. This yields a practical learning framework which significantly advances the state-of-the-art in inference for DGPs, and enables accurate quantification of uncertainty. We extensively showcase the scalability and performance of our proposal on several datasets with up to 8 million observations, and various DGP architectures with up to 30 hidden layers.

A python / TensorFlow implementation can be found here: https://github.com/mauriziofilippone/deep_gp_random_features

AutoGP: Exploring the Capabilities and Limitations of Gaussian Process Models by Karl Krauth, Edwin V. Bonilla, Kurt Cutajar, Maurizio Filippone

We investigate the capabilities and limitations of Gaussian process models by jointly exploring three complementary directions: (i) scalable and statistically efficient inference; (ii) flexible kernels; and (iii) objective functions for hyperparameter learning alternative to the marginal likelihood. Our approach outperforms all previously reported GP methods on the standard MNIST dataset; performs comparatively to previous kernel-based methods using the RECTANGLES-IMAGE dataset; and breaks the 1% error-rate barrier in GP models using the MNIST8M dataset, showing along the way the scalability of our method at unprecedented scale for GP models (8 million observations) in classification problems. Overall, our approach represents a significant breakthrough in kernel methods and GP models, bridging the gap between deep learning approaches and kernel machines.

and here is a recent presentation by one of the author: "Practical and Scalable Inference for Deep Gaussian Processes"

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

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.

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation

We have covered Manopt before several times ( tag Manopt). It now comes to Python. From the paper:

Further successful applications of optimization on manifolds include matrix completion tasks (Vandereycken, 2013; Boumal and Absil, 2015), robust PCA (Podosinnikova et al., 2014), dimension reduction for independent component analysis (ICA) (Theis et al., 2009), kernel ICA (Shen et al., 2007) and similarity learning (Shalit et al., 2012).
Many more applications to machine learning and other elds exist. While a full survey on the usefulness of these methods is well beyond the scope of this manuscript, we highlight that at the time of writing, a search for the term \manifold optimization" on the IEEE Xplore Digital Library lists 1065 results; the Manopt toolbox itself is referenced in 90 papers indexed by Google Scholar.

It looks like that at the time of this writing, it is more like 126 times that the Manopt toolbow has been referenced in Google Scholar.

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation by  James Townsend, Niklas Koep, Sebastian Weichwald

Optimization on manifolds is a class of methods for optimization of an objective function, subject to constraints which are smooth, in the sense that the set of points which satisfy the constraints admits the structure of a differentiable manifold. While many optimization problems are of the described form, technicalities of differential geometry and the laborious calculation of derivatives pose a significant barrier for experimenting with these methods.
We introduce Pymanopt (available at this https URL), a toolbox for optimization on manifolds, implemented in Python, that---similarly to the Manopt Matlab toolbox---implements several manifold geometries and optimization algorithms. Moreover, we lower the barriers to users further by using automated differentiation for calculating derivative information, saving users time and saving them from potential calculation and implementation errors.

 
 The implementation is here: https://pymanopt.github.io/

 

h/t Nando. 
 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
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.

FMR: Fast randomized algorithms for covariance matrix computations - implementation -

The full poster is here.

from the poster: 

Sources are available online as part of the open-source package FMR. They can be downloaded for free at the following address https://gforge.inria.fr/projects/fmr 
Dependencies FMR relies on 

• ScalFMM [1] for performing fast multipole matrix multiplication in parallel (in shared and distributed memory) 
• MKL for dense linear algebra and FFT 
• Scotch or CClusteringLib for partitionning Features The package provides: 
• routines for generating Gaussian Random Fields based on

• standard LRA: Cholesky Decomposition, SVD or FFT for regular grids. 

• randomized LRA: RandSVD and Nystrom method with uniform or leverage score-based sampling.

• a variety of correlation kernels: Mat´ern, Spherical model, Oseen-Gauss.

• a Python interface for MDS using Randomized SVD or Nystrom
• a Matlab interface for Ensemble Kalman Filtering

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
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.

FastEmbed: Compressive spectral embedding: sidestepping the SVD - implementation -

From the paper:

"...In this paper, we tackle these scalability bottlenecks by focusing on what embeddings are actually used for: computing ℓ2-based pairwise similarity metrics typically used for supervised or unsupervised learning. For example, K-means clustering uses pairwise Euclidean distances, and SVM-based classification uses pairwise inner products. We therefore ask the following question: “Is it possible to compute an embedding which captures the pairwise euclidean distances between the rows of the spectral embedding E= [f(σ1)u1···f(σk)uk], while sidestepping the computationally expensive partial SVD?” We answer this question in the affirmative by presenting a compressive algorithm which directly computes a low-dimensional embedding..."

Compressive spectral embedding: sidestepping the SVD by Dinesh Ramasamy, Upamanyu Madhow

Spectral embedding based on the Singular Value Decomposition (SVD) is a widely used "preprocessing" step in many learning tasks, typically leading to dimensionality reduction by projecting onto a number of dominant singular vectors and rescaling the coordinate axes (by a predefined function of the singular value). However, the number of such vectors required to capture problem structure grows with problem size, and even partial SVD computation becomes a bottleneck. In this paper, we propose a low-complexity it compressive spectral embedding algorithm, which employs random projections and finite order polynomial expansions to compute approximations to SVD-based embedding. For an m times n matrix with T non-zeros, its time complexity is O((T+m+n)log(m+n)), and the embedding dimension is O(log(m+n)), both of which are independent of the number of singular vectors whose effect we wish to capture. To the best of our knowledge, this is the first work to circumvent this dependence on the number of singular vectors for general SVD-based embeddings. The key to sidestepping the SVD is the observation that, for downstream inference tasks such as clustering and classification, we are only interested in using the resulting embedding to evaluate pairwise similarity metrics derived from the euclidean norm, rather than capturing the effect of the underlying matrix on arbitrary vectors as a partial SVD tries to do. Our numerical results on network datasets demonstrate the efficacy of the proposed method, and motivate further exploration of its application to large-scale inference tasks.

A Python implementation of FastEmbed is available at: https://bitbucket.org/dineshkr/fastembed/src/NIPS2015

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
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.

Random Mappings Designed for Commercial Search Engines - implementation -

Changing various non-text documents into vectors that have the characteristics of vector texts using thresholded random projections is the goal of today's paper. From the paper:

Although proving that our random mapping scheme works is involved, the scheme is remarkably simple. Our corpus X is a finite collection of vectors in R^d, normalized to have unit l_2 norm. To transform each vector in X, multiply each vector by a random matrix, then threshold each element.

Random mappings designed for commercial search engines by Roger Donaldson, Arijit Gupta, Yaniv Plan, Thomas Reimer

We give a practical random mapping that takes any set of documents represented as vectors in Euclidean space and then maps them to a sparse subset of the Hamming cube while retaining ordering of inter-vector inner products. Once represented in the sparse space, it is natural to index documents using commercial text-based search engines which are specialized to take advantage of this sparse and discrete structure for large-scale document retrieval. We give a theoretical analysis of the mapping scheme, characterizing exact asymptotic behavior and also giving non-asymptotic bounds which we verify through numerical simulations. We balance the theoretical treatment with several practical considerations; these allow substantial speed up of the method. We further illustrate the use of this method on search over two real data sets: a corpus of images represented by their color histograms, and a corpus of daily stock market index values.

Python codes used to generate results of that paper, including running example searches using the Whoosh search engine for Python, is here at: https://gitlab.com/dgpr-sparse-search/code

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
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.

Raking the Cocktail Party - implementation -

Following up on this morning's thesis here is an implementation:

 

Raking the Cocktail Party by Dokmanic, Ivan; Scheibler, Robin; Vetterli, Martin

We present the concept of an acoustic rake receiver—a microphone beamformer that uses echoes to improve the noise and interference suppression. The rake idea is well-known in wireless communications; it involves constructively combining different multipath components that arrive at the receiver antennas. Unlike spread-spectrum signals used in wireless communications, speech signals are not orthogonal to their shifts. Therefore, we focus on the spatial structure, rather than temporal. Instead of explicitly estimating the channel, we create correspondences between early echoes in time and image sources in space. These multiple sources of the desired and the interfering signal offer additional spatial diversity that we can exploit in the beamformer design. We present several “intuitive” and optimal formulations of acoustic rake receivers, and show theoretically and numerically that the rake formulation of the maximum signal-to-interference-and-noise beamformer offers significant performance boosts in terms of noise and interference suppression. Beyond signal-to-noise ratio, we observe gains in terms of the perceptual evaluation of speech quality (PESQ) metric for the speech quality. We accompany the paper by the complete simulation and processing chain written in Python. The code and the sound samples are available online at http://lcav.github.io/AcousticRakeReceiver/.

      Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Factorization Machines implementation in Theano

A reader on Reddit pointed out his implementation of the fastFM: A Library for Factorization Machines - implementation - in Theano: It is at: https://github.com/instagibbs/FactorizationMachine

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

fastFM: A Library for Factorization Machines - implementation -

fastFM: A Library for Factorization Machines by Immanuel Bayer

Factorization Machines (FM) are only used in a narrow range of applications and are not part of the standard toolbox of machine learning models. This is a pity, because even though FMs are recognized as being very successful for recommender system type applications they are a general model to deal with sparse and high dimensional features. Our Factorization Machine implementation provides easy access to many solvers and supports regression, classification and ranking tasks. Such an implementation simplifies the use of FM's for a wide field of applications. This implementation has the potential to improve our understanding of the FM model and drive new development.

from the introduction to the lirary:

(i) Easy interfacing for dynamic and interactive languages such as R, Python and Matlab.
(ii) A Python interface that allows interactive work. (iii) A publicly available testsuite that
strongly simpli es modi cations or adding of new features. (iv) Code is released under the
BSD-license which allows the integration in (almost) any open source project.

 The GitHub repository is here: https://github.com/ibayer/fastFM

Related:Thierry Silbermann presented libFM & Factorization Machines at the Paris Machine Learning #6 Season 2. His presentaton can be from 1:24:45 to 2:10:42 minutes into the video.



Thierry Silbermann, University of Konstanz, libFM & Factorization Machines

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

AutoML Challenge: Python Notebooks for Round 1 and more...

In  the Sunday Morning Insight entry entitled The Hardest Challenges We Should be Unwilling to Postpone,  I mentioned a challenge set up by Isabelle Guyon entitled the AutoML challenge ( http://codalab.org/AutoML, her presentation is here). In short, the idea is to have a Kaggle like challenge that features several datasets of increasing difficulty and see how algorithm entries fare with these different datasets. Deep down, the algorithm needs to pay attention to its own running time and have a nice way of automatically select relevant features.

With Franck, we decided to use the mighty power of the large membership of the Paris Machine Learning meetup (Top 5 in the world) to help out in the setting up of a day long hackaton so that local teams could participate in the challenge. Currently round 1 of the challenge is over we are currently in the Tweakathon1 stage where you can submit codes that will eventually be run automatically on May 15 for AutoML2. From here:

Tweakathon1 

Continue practicing on the same data (the phase 1 data are now available for download from the 'Get Data' page). In preparation for phase 2, submit code capable of producing predictions on both VALIDATION AND TEST DATA. The leaderboard shows scores on phase 1 validation data only.

AutoML2


Start: May 15, 2015, 11:59 p.m.

Description: INTERMEDIATE phase on multiclass classification problems. Blind test of the code on NEW DATA: There is NO NEW SUBMISSION. The last code submitted in phase 1 is run automatically on the new phase 2 datasets. [+] Prize winning phase.


Tweakathon2  

Start: May 16, 2015, 11:59 p.m.

Description: Continue practicing on the same data (the data are now available for download from the 'Get Data' page). In preparation for phase 3, submit code capable of producing predictions on both VALIDATION AND TEST DATA. The leaderboard shows scores on phase 2 validation data only. 

Here are some of the presentations made during the hackaton and some of the attendant python notebooks released for tweakaton 1:

• Isabelle Guyon and Lukasz Romaszko (ChaLearn): Presentation of the AutoML challenge. Tips to solve it and win! 
• Olivier Grisel (INRIA): How to use Scikit-Learn to solve machine learning problems. 
• iPython notebook example given in talk
• iPython notebook to solve round 1of the AutoML challenge
• Julien Demouth (NVIDIA): Deep Neural Networks and GPUs.

The page for the hackaton is here. A big thank you to Pierre Roussel for hosting us at ESPCI ParisTech and to the coaches

• Delphine Le, Ecole Centrale Paris
• Djalel Benbouzid, Univ. Paris Saclay
• Bogdan-Ionut Cirstea, ENST, Paris
• Olivier Grisel, INRIA, Paris
• Lovro Ilijasic, Univ. Paris Saclay
• Lukasz Romazko, CVC Barcelona, ChaLearn

Other links:

• NVIDIA machine learning
• Introduction paper (accepted to IJCNN 2015)
• Sample code for the hackathon (do not submit as is, run the code on your local computer, then submit results).
• GPU track instructions
• Sklearn Kaggle examples

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Python version of SPGL1 - implementation -

David Relyea just let me know of his porting the famous SPGL1 solver to Python, woohoo !

Hi Igor,


I've entirely ported the Matlab version of SPGL1 to python. It has full functionality (it heavily leverages numpy) and I haven't caught any bugs in it at all, so I'm letting everyone know. I got the ok from Michael Friedlander to distribute it (under the same license, of course). It's at https://github.com/drrelyea/SPGL1_python_port. Please let people know!

I also intend to clean it up a bit and have it added to scikit-learn, as it's the fastest L1 solver I know of that can handle complex numbers.


All the best,


David Relyea 

Thanks David !

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

MORESANE: MOdel REconstruction by Synthesis-ANalysis Estimators. A sparse deconvolution algorithm for radio interferometric imaging - implementation

What is really happening with SKA is fascinating: This paper and others are using the latest and greatest reconstruction algorithm in compressive sensing to figure out some of this future telescope's technical specifications and data chains. 

MORESANE: MOdel REconstruction by Synthesis-ANalysis Estimators. A sparse deconvolution algorithm for radio interferometric imaging by Arwa Dabbech, Chiara Ferrari, David Mary, Eric Slezak, Oleg Smirnov, Jonathan S. Kenyon

The current years are seeing huge developments of radio telescopes and a tremendous increase of their capabilities. Such systems make mandatory the design of more sophisticated techniques not only for transporting, storing and processing this new generation of radio interferometric data, but also for restoring the astrophysical information contained in such data. In this paper we present a new radio deconvolution algorithm named MORESANE and its application to fully realistic simulated data of MeerKAT, one of the SKA precursors. This method has been designed for the difficult case of restoring diffuse astronomical sources which are faint in brightness, complex in morphology and possibly buried in the dirty beam's side lobes of bright radio sources in the field. MORESANE is a greedy algorithm which combines complementary types of sparse recovery methods in order to reconstruct the most appropriate sky model from observed radio visibilities. A synthesis approach is used for the reconstruction of images, in which the synthesis atoms representing the unknown sources are learned using analysis priors. We apply this new deconvolution method to fully realistic simulations of radio observations of a galaxy cluster and of an HII region in M31. We show that MORESANE is able to efficiently reconstruct images composed from a wide variety of sources from radio interferometric data. Comparisons with other available algorithms, which include multi-scale CLEAN and the recently proposed methods by Li et al. (2011) and Carrillo et al. (2012), indicate that MORESANE provides competitive results in terms of both total flux/surface brightness conservation and fidelity of the reconstructed model. MORESANE seems particularly well suited for the recovery of diffuse and extended sources, as well as bright and compact radio sources known to be hosted in galaxy clusters.

 The implementation of MORSEANE is on GitHub: https://github.com/ratt-ru/PyMORESANE

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Zero SR1 quasi-Newton method - implementation -

From Stephen Becker's webpage here is;

Zero SR1 quasi-Newton method

Background

The zeroSR1 package is based on a proximal quasi-Newton algorithm to solve

where is a smooth convex function and is a (possibly non-smooth, and possibly infinite) convex function such that the

• the proximity operator is easy to compute,
  
• the proximity operator is separable in the components of the variable, and
  
• the proximity operator is piecewise linear.
  

Exploiting the nature of , we show in 'A quasi-Newton proximal splitting method’ (Becker, Fadili; NIPS 2012) that one can also compute the proximity operator of in a scaled norm:

where is a diagonal matrix, is a vector so that is a rank-1 matrix, and is .

Because we can efficiently solve for the scaled prox, it opens up the possibility of a quasi-Newton method. The SR1 update is a rank-1 update, and by using a 0-memory version, the updates to the inverse Hessian are in exactly the form of .

This means that for the same cost as a proximal gradient method (or an accelerated one, like FISTA), we can incorporate second order information, and the method converges very quickly.

Types of non-smooth terms we can handle

The non-smooth term can be infinite valued; for example, it may be an indicator function of a set. The indicator function of a set is denoted

Equivalently, we are enforcing the constraint in the optimization problem.

We can solve the scaled prox of the following in time (compared to time for the regular prox) for inputs of dimension :

Function	mathematical representation
l1 norm
non-negativity constraints	,
l1 norm and non-negativity
box constraints	,
norm ball	,
hinge loss

Code

We have put a Matlab/Octave implementation on github, under the BSD 3-clause license. If you are interested in contributing a version in python or R, we will be glad to assist.

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.