LSR: Robust and Efficient Subspace Segmentation via Least Squares Regression - implementation -

As Canyi Lu mentions to me by email, the following implementation and paper "propose a general framework for achieving a block diagonal affinity matrix for subspace clustering." It was just added to the Advanced Matrix Factorization Jungle page.

Robust and Efficient Subspace Segmentation via Least Squares Regression by Canyi Lu, Hai Min, Zhong-Qiu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan (and an attendant poster and slides)

This paper studies the subspace segmentation problem which aims to segment data drawn from a union of multiple linear subspaces. Recent works by using sparse representation, low rank representation and their extensions attract much attention. If the subspaces from which the data drawn are independent or orthogonal, they are able to obtain a block diagonal affinity matrix, which usually leads to a correct segmentation. The main differences among them are their objective functions. We theoretically show that if the objective function satisfies some conditions, and the data are sufficiently drawn from independent subspaces, the obtained affinity matrix is always block diagonal. Furthermore, the data sampling can be insufficient if the subspaces are orthogonal. Some existing methods are all special cases. Then we present the Least Squares Regression (LSR) method for subspace segmentation. It takes advantage of data correlation, which is common in real data. LSR encourages a grouping effect which tends to group highly correlated data together. Experimental results on the Hopkins 155 database and Extended Yale Database B show that our method significantly outperforms state-of-the-art methods. Beyond segmentation accuracy, all experiments demonstrate that LSR is much more efficient.

The attendant code is here.

Thank you Canyi !

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.

IRNN: Generalized Nonconvex Nonsmooth Low-Rank Minimization - implementation -

 Generalized Nonconvex Nonsmooth Low-Rank Minimization by Canyi Lu, Zhouchen Lin, Shuicheng Yan.

As surrogate functions of L0-norm, many nonconvex penalty functions have been proposed to enhance the sparse vector recovery. It is easy to extend these nonconvex penalty functions on singular values of a matrix to enhance low-rank matrix recovery. However, different from convex optimization, solving the nonconvex low-rank minimization problem is much more challenging than the nonconvex sparse minimization problem. We observe that all the existing nonconvex penalty functions are concave and monotonically increasing on [0,∞). Thus their gradients are decreasing functions. Based on this property, we propose an Iteratively Reweighted Nuclear Norm (IRNN) algorithm to solve the nonconvex nonsmooth low-rank minimization problem. IRNN iteratively solves a Weighted Singular Value Thresholding (WSVT) problem. By setting the weight vector as the gradient of the concave penalty function, the WSVT problem has a closed form solution. In theory, we prove that IRNN decreases the objective function value monotonically, and any limit point is a stationary point. Extensive experiments on both synthetic data and real images demonstrate that IRNN enhances the low-rank matrix recovery compared with state-of-the-art convex algorithms.

The attendant code is here.

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.

CPCP: Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods - implementation -

We mentioned Frank-Wolfe recently: 

Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods by Cun Mu, Yuqian Zhang, John Wright, Donald Goldfarb

Recovering matrices from compressive and grossly corrupted observations is a fundamental problem in robust statistics, with rich applications in computer vision and machine learning. In theory, under certain conditions, this problem can be solved in polynomial time via a natural convex relaxation, known as Compressive Principal Component Pursuit (CPCP). However, all existing provable algorithms for CPCP suffer from superlinear per-iteration cost, which severely limits their applicability to large scale problems. In this paper, we propose provable, scalable and efficient methods to solve CPCP with (essentially) linear per-iteration cost. Our method combines classical ideas from Frank-Wolfe and proximal methods. In each iteration, we mainly exploit Frank-Wolfe to update the low-rank component with rank-one SVD and exploit the proximal step for the sparse term. Convergence results and implementation details are also discussed. We demonstrate the scalability of the proposed approach with promising numerical experiments on visual data.

The implementation is here. CPCP has been added to the Advanced Matrix Factorization Jungle under the Matrix Compressive Sensing heading.

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.

Deep ConvNets; "Astounding" baseline for vision

Last night, Pierre Sermanet gave a talk on OverFeat and ConvNets. The meetup was triggered by one of Pierre's post on Google+ where he mentioned an ArXiv preprint where some folks at KTH [2] used features from OverFeat [1,3] and an SVM to get results they called "astounding" and said so in the title of the paper ( CNN Features off-the-shelf: an Astounding Baseline for Recognition ). The use of such wording is rare (If you recall similar words such as "stunning" or "quite striking" were used for a different 2011 paper in compressive sensing). So at the Paris Machine Learning Meetup group, we decided to have an impromptu specialist talk/meetup while Pierre was around. Gabriel Synnaeve got his lab to co-sponsor the talk that was eventually held at Normale Sup. Pierre made available the two most important slides of his talk here.

Mentionned in the talk besides OverFeat were:

• Clarifai and 
• Caffe

More on this later and if anything it tells me the sensor designers ought to pay more and more attention to this type of breakthrough.

Thank you Pierre for the talk, and thanks to Gabriel for co-organizing the meetup. Other thanks go to Criteo, DoJoEvents and Alexandre for trying hard to fit our short fuse meeting with their hosting capabilities. About 60 people showed up with a two days notice !

I am not sure the Hangout on Air worked and the video from my GoPro has very little sound.

[1] OverFeat: Integrated Recognition, Localization and Detection using Convolutional Networks, Pierre Sermanet, David Eigen, Xiang Zhang, Michael Mathieu, Rob Fergus, Yann LeCun, http://arxiv.org/abs/1312.6229

[2] CNN Features off-the-shelf: an Astounding Baseline for Recognition, Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, Stefan Carlsson, http://arxiv.org/abs/1403.6382

[3] OverFeat, http://cilvr.nyu.edu/doku.php?id=code:start

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.

From Direct Imaging to Machine Learning ... a rapid panorama (JIONC 2014)

I have attended, for the past three years, the "Journées d'imagerie optique non-conventionnelle" (or JIONC for short) organized at ESPCI (don't look, there is currently no website for these meetings) and felt that the generic dichotomy of looking at sensors and then reconstruction solvers needed some perspective. So I decided to put in an abstract for a presentation two hours before the deadline. As it turns out, the committee was overwhelmed with abstracts this time (more than double the usual number) and they had to deal with different constraints, one of which was a time constraint. I was accepted for a poster which was not what I had expected. Then again, it was pretty much a blessing in disguise as I somehow honed my story several times with the few unwitting people who stumbled close to the dark lit corner of the room where poster was located. To them, thank you and sorry at the same time :-). 

The whole "poster" is located here: From Direct Imaging to Machine Learning ... a rapid panorama. Any insight on how it could be better presented is more than welcome. Many shortcuts were taken, the reference section is dismal but the point was trying to give a bird's eye view of fields that are currently on a collision course, especially if you look at them with the lens (pun intended) of advanced matrix factorizations.

JIONC was the same day as the IoT presentation so it took me a little while to clean up the original poster.

In the meantime, few readers have pointed me to the TechReview on Patrick Gill's lensless camera, I'll come to that later because it is a nice illustration of some of the comments made during the presentation of this poster. 

Tonight a 7:00pm, Pierre Sermanet is in Paris and will talk to us about OverFeat [1, 3]. Why ? because as mentioned in the poster, there is a convergence between deep learning and generic sensing. In particular, in this case, you rarely see the word "astounding" from a different team working with your approach [2]. Hence the invitation for him to speak, two days ago, to our ML and not so ML people.

As an aside, if Yann LeCun, Yoshua Bengio or Andrew Ng or any of the big thoughts leaders in ML are bored in Paris and want to give a talk to our audience, it looks like that with a 2-day notice, we can get a location and more than 150 people to attend. 

[1] OverFeat: Integrated Recognition, Localization and Detection using Convolutional Networks, Pierre Sermanet, David Eigen, Xiang Zhang, Michael Mathieu, Rob Fergus, Yann LeCun, http://arxiv.org/abs/1312.6229

[2] CNN Features off-the-shelf: an Astounding Baseline for Recognition, Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, Stefan Carlsson, http://arxiv.org/abs/1403.6382

[3] OverFeat, http://cilvr.nyu.edu/doku.php?id=code:start

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.

Bayesian Pursuit Algorithms - implementation -

Bayesian Pursuit Algorithms by Cedric Herzet, Angélique Drémeau

This paper addresses the sparse representation (SR) problem within a general Bayesian framework. We show that the Lagrangian formulation of the standard SR problem, i.e. $\x^\star=\argmin_\x \lbrace \| \y-\D\x\|_2^2+\lambda\| \x\|_0 \rbrace$, can be regarded as a limit case of a general maximum a posteriori (MAP) problem involving Bernoulli-Gaussian variables. We then propose different tractable implementations of this MAP problem that we refer to as ''Bayesian pursuit algorithms". The Bayesian algorithms are shown to have strong connections with several well-known pursuit algorithms of the literature (e.g., MP, OMP, StOMP, CoSaMP, SP) and generalize them in several respects. In particular, i) they naturally allow for atom deselection; ii) they can include any prior information about the probability of occurrence of each atom within the selection process; iii) they can encompass the estimation of unkown model parameters into their recursions.

Attendant implementations are located here.

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.

KNIFE: Automatic Feature Selection via Weighted Kernels and Regularization - implementation -

One wonders if there would be a way to randomize some part of this algorithm:

Automatic Feature Selection via Weighted Kernels and Regularization by Genevera I. Allen

Selecting important features in non-linear kernel spaces is a difficult challenge inboth classification and regression problems. We propose to achieve feature selectionby optimizing a simple criterion: a feature-regularized loss function. Features withinthe kernel are weighted, and a lasso penalty is placed on these weights to encouragesparsity. We minimize this feature-regularized loss function by estimating the weightsin conjunction with the coefficients of the original classification or regression problem,thereby automatically procuring a subset of important features. Our algorithm, KerNel Iterative Feature Extraction (KNIFE), is applicable to a wide variety of kernelsand high-dimensional kernel problems. In addition, a modification of KNIFE gives acomputationally attractive method for graphically depicting non-linear relationshipsbetween features by estimating their feature weights over a range of regularizationparameters. We demonstrate the utility of KNIFE in selecting features through simulations and examples for both kernel regression and support vector machines. Feature path realizations also give graphical representations of important features and the nonlinear relationships among variables.

The attendant implementation is here.



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.

Another Sighting of Citing Nuit Blanche

After the sighting at Stanford, here is new one found by Laurent Daudet who took the photo of Maxime Dahan's presentation at IPGP.

Next up, world domination mmmuuuaaaahhhhhh.....

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.

Summary of Contribution: Compressed sensing with linear correlation between signal and measurement noise - implementation -

Thomas Arildsen just wrote a blog entry, here how it starts:

Compressed sensing with linear correlation between signal and measurement noise

by Thomas Arildsen

Torben Larsen and I have recently published a paper, “Compressed sensing with linear correlation between signal and measurement noise” in EURASIP Signal Processing. This post is an attempt and a sort of experiment to provide a front page summarizing the paper’s contributions and providing an overview of available versions of the paper and its accompanying code...

The rest is here.

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.

SKA as an Atmosphere Monitoring Station ? - Part deux -

In yesterday's post I mentioned that there would be more about SKA (remember this entry on SKA as an Atmosphere Monitoring Station ?)

Well for one, Ludwig Schwardt mentioned this in the comment section

Hi njh and Igor,

As someone who works on the SKA and on one of its pathfinder instruments (MeerKAT), as well as on the DOME project advertising the postdoc position, I feel obliged to respond :-)

Radio telescopes *do* operate during the day, even if it is just to make the optical astronomers jealous (although they have the last laugh when you see how weak astronomical radio signals are). The Sun is not that big a problem to first order as our typical dishes are only sensitive to a one-degree patch on the sky and they can avoid the Sun during observations. Some very sensitive observations might still need to remove a tiny contribution from the Sun by the appropriate modelling.

A ballpark number for the solar energy received on the Earth's surface is 1 kW per square meter. A square kilometer would therefore receive 1 GW. Given that the Sun is only up half the time and blithely ignoring clouds and other inefficiencies we have the potential for a 500 MW power plant. While this is large for a solar plant, it is below average for a coal-fired plant. The project will also need substantial additional funding to turn it into a solar plant. Maybe an idea for when the SKA retires? :-)

To comment on Igor's statement that normal operation of the SKA during daylight ought to provide some information on the atmosphere above it: this is true. The radio signals to be received by the SKA (during the day or night) will mostly be affected by disturbances in the ionosphere and to a lesser extent by water vapour in the troposphere. These (unwanted!) phase drifts and attenuations have to be modelled and calibrated out to obtain a clear image. This is typically done in conjunction with direct atmospheric measurements using GNSS satellites and water vapour radiometers.

Thank you  Ludwig . Yes, somebody's noise is someone else's signal, it's just a different convolution. By the same token, I also came across this preprint,

Non-linear Kalman filters for calibration in radio interferometry by Cyril Tasse

We present a new calibration scheme based on a non-linear version of Kalman filter that aims at estimating the physical terms appearing in the Radio Interferometry Measurement Equation (RIME). We enrich the filter's structure with a tunable data representation model, together with an augmented measurement model for regularization. We show using simulations that it can properly estimate the physical effects appearing in the RIME. We found that this approach is particularly useful in the most extreme cases such as when ionospheric and clock effects are simultaneously present. Combined with the ability to provide prior knowledge on the expected structure of the physical instrumental effects (expected physical state and dynamics), we obtain a fairly cheap algorithm that we believe to be robust, especially in low signal-to-noise regime. Potentially the use of filters and other similar methods can represent an improvement for calibration in radio interferometry, under the condition that the effects corrupting visibilities are understood and analytically stable. Recursive algorithms are particularly well adapted for pre-calibration and sky model estimate in a streaming way. This may be useful for the SKA-type instruments that produce huge amounts of data that have to be calibrated before being averaged.

as a side note, one can read in the paper the following tidbit:

It is important to note that deconvolution algorithms, are also Physics-based solvers estimating the sky brightness, potentially taking DDE calibration solution into account (Bhatnagar et al. 2008, 2013; Tasse et al. 2013). Latest imaging solvers can also estimate spectral energy distribution parameters (Rau & Cornwell 2011; Junklewitz et al. 2014). Most of these imaging algorithms are now well understood in the framework of compressed sensing theory (see McEwen & Wiaux 2011, for a review). Their goals, constrains and methods are however very different from purely calibration-related algorithms, and we will not discuss them further in this paper.

I would not be so dismissive, other people are taking a stab at blind calibration issues. There can't that many stars. The initial post was a SKA job announcement, that might be a way to look into this calibration issue with constraints of a new kind. I am saying this but I have no insider's knowledge on the what the job really entails.

Of related interest:

The other videos on SKA related calibration and computation issues can be found in the Calim 2012 workshop YoutTube channel.

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.