Friday, May 29, 2015

Reader's Digest: Gaussian vs Structured Projections, Improving A2I implementations, Kaczmarz method, Xampling the Future

Following up on this recent blog entry entitled Compressed Nonnegative Matrix Factorization is Fast and Accurate, I went ahead and asked the authors Mariano Tepper and Guillermo Sapiro a dumb question:

Dear Mariano and Guillermo,

....I recently featured your latest interesting preprint on "Compressed Nonnegative Matrix Factorization is Fast and Accurate".

I noted that you made a specific statement that gaussian projections were not as accurate as the structured projections you suggest in the paper. I was wondering the following, can a similar accuracy be obtained by gaussian random projections provided there are more projections (compared to the structured ones you have devised) ? I realize it sounds like a silly statement but I am wondering if during your different runs you had observed that Gaussian projections could indeed reach the accuracy of your structured projection with a reasonable additional set of projections (the key part of the question obviously resides in "reasonable"). Thanks in advance for your time.

Mariano was kind enough to answer:

Hi Igor,

Thanks for featuring our paper! ...

Your intuition is right, adding more random projections (i.e., using less compression) leads to improved results. We have done many experiments regarding this particular point. Let me summarize the two key points from our observations:
  • In general, MANY more random projections need to be added, not just a few.
  • The amount of compression varies significantly with the data being used (some data are harder to compress). This variability is very much attenuated when using compression techniques that exploit the data structure.

I attach a simple plot, showing for a synthetic dataset how the results vary with the compression level (the compression level is the number of projections). In this case, the increase in performance has a quite weak dependency on the number of projections. These type of experiments were left out of our journal submission because of space constraints.

Hope this clarifies a bit more your comment.

 On another interaction Edmar Candeia Gurjao mentioned 

Hi Igor,

we have just published a paper in the 2015 IEEE International Instrumentation and Measurement Technology Conference I2MTC entitled "Using Synchronism Pulse to Improve A2I Implementations" V. L. Reis, E. C. Gurjão and R. C. S. Freire. It presents our first contribution towards a reconfigurable Analog to Information Converter, and I am sending the poster we present in the conference, could you publish in Nuit Blanche? Thanks,

Sure Edmar ! The poster is here.

In the comment section of the blog entry on  "Faster Randomized Kaczmarz", Surya wondered:

I am curious (and at the same time trying to check) if Kaczmarz method is used as an alternative to methods like conjugate gradient or LSQR when solving sparse least squares problems.
Finally, we should more about it later but I received an announcement for the SAMPL 2015 workshop with the title "Xampling the Future" on June 22nd at the Technion. I am sure more information will show up on Yonina's site very soon !
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.

No comments: