GraphLab and GraphChi group on LinkedIn

Danny just started the GraphLab and GraphChi group on LinkedIn. If you want to be part of that disruptive discussion, we may want to join. 

See also: GraphLab workshop, Why should you care ?

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.

TED Talk: Ramesh Raskar: Imaging at a trillion frames per second

Ramesh just gave a wonderful talk a TED this past July entitled Imaging at a trillion frames per second.

If you recall reconstructing a scene entailed solving a compressive sensing problem (see Reconstruction of hidden 3D shapes using diffuse reflections and Flutter Shutter Video Camera for Compressive Sensing and Strobing high resolution camera with picosecond time resolution). As Ramesh points out in his talk there are now more data available directly from these sites: Femto-Photography: Visualizing Photons in Motion at a Trillion Frames Per Second and CORNAR: Looking Around Corners using Femto-Photography.

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.

Around the blogs in 80 summer hours

This week we featured a few implementation and a new hardware:

• Compressive Sensing with Local Geometric Features: Hardware and Implementation
• DORE j'ADORE: Sparse signal reconstruction via ECME hard thresholding - implementation -
• A Sub-Nyquist Radar Prototype: Hardware and Algorithms

A very nice review of results prior 2004 was featured in The Invention of Compressive Sensing and Recent Results. We also two CFPs: Workshop on Analysis Operator Learning vs. Dictionary Learning: Fraternal Twins in Sparse Modeling and Fifth IEEE International Conference on Computational Photography (ICCP)

We wondered if A Compressive Sensing Capability for CheMin was onboard Curiosity ? (I have sent an email to the PI) and whether the microbiome should be of interest for the design of new sensors (Sparsity in Everything: The Gut Microbiome). Several authors mentioned to us their preprints or papers in the Nuit Blanche Mailbag:

• Sparsity Averaging for Compressive Imaging and Reweighted sparse deconvolution for high angular resolution diffusion MRI
• Improving Noise Robustness in Subspace-based Joint Sparse Recovery

We also found out that compressive sensing talks in seismic are worth it in No cookies for you at the University of Wisconsin-Madison and figured out a way to perform a Kinect Installation on a PC with Windows XP. Finally, I spent some time pulling out the statistics for this blog in Nuit Blanche by the Numbers

The other very interesting entries of the week were:

• Anna summarizes the Open problems from SPARC Workshop
• Danny tells us about Collaborative filtering with GraphChi
• Masaaki talks about Optimal Design of Delta-Sigma Modulators
• Andrew wants to share with us How [he] think about mixture models
• Larry tells us about P-values Gone Wild and Multiscale Madness 
• Dirk tells us about the reception at ISMP in Berlin  (with a twist in CS and Matrix Factorization)
• Rich tells us that the OpenStax College’s Free Textbooks Will Save Students $1M This Fall
• Hao' tells us how to Use IEEE Xplore to do a field study
• Andrej explores Khan Academy and Computer Science
• Randy features ''The Truth About Terahertz" (reposted from spectrum and this reminded me exactly the types of issues we have to deal with when we use neutrons to perform tomography: Here is a good introduction on the subject:

Image Credit: NASA/JPL-Caltech
This image was taken by Navcam: Left A (NAV_LEFT_A) onboard NASA's Mars rover Curiosity on Sol 12 (2012-08-18 11:38:26 UTC) .
Full Resolution

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.

Nuit Blanche by the Numbers

Today marks the fourth year since the Compressive Sensing Group on LinkedIn was founded and 1,709 people are part of that conversation.

From the stats of the discussions and comments, it looks like some activity started once we reached a critical mass of about 400 people  

We are today also reaching that same number of 403 for the Advanced Matrix Factorization group, let us hope that some conversation gets going there as recommender systems are taking a larger place in much of the IT world these days. 

There are also two smaller groups that might be of interest to the readers of this blog: The Calibration Club with 26 people and the Gaussian Belief Propagation: Theory and Practice with 60 people. In the former, we are interested in issues of sensor and hardware calibration beyond least squares, i.e. what are the new methods using sparsity and related low-rank concepts to perform better faster and calibration of sensors and different hardware. The latter group is focused on issues related to all things related to what is now called AMP solvers and their applications.

If you like Nuit Blanche in general and the diverse conversations it has enabled, I don't mind if you write a small recommendation for me on LinkedIn. 

I also stumbled on another "milestone" while adding up the three feeds from feedburner (they all subscribe to the same stream), Nuit Blanche is now followed by  and  and ..As of yesterday, it added up to 2000 feed readers while 440 readers receive every entries in their mailboxes every day.

 you can subscribe to the Nuit Blanche feed here.

The Google +1 amount to 37 for Nuit Blanche and went as high as 8 for this entry.

Eventually, the real question is: when is Nuit Blanche going to reach 5 million page views ?

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 Compressive Sensing Capability for CheMin aboard Curiosity ?

While reading through the list of Instruments currently on Curiosity, I came across this one:

Chemistry &; Mineralogy (CheMin)

PI: David Blake, NASA Ames Research Center

Contributions of CheMin to MSL Science Objectives

An important science goal of the MSL mission is to identify and characterize past or present habitable environments as recorded in sediments and rocks. CheMin is a definitive mineralogy instrument that will identify and quantify the minerals present in rocks and soil delivered to it by the Sample Acquisition, Sample Processing and Handling (SA/SPaH) system. By determining the mineralogy of rocks and soils, CheMin will assess the involvement of water in their formation, deposition, or alteration. In addition, CheMin data will be useful in the search for potential mineral biosignatures, energy sources for life or indicators of past habitable environments. CheMin can unequivocally identify and quantify minerals above its detection limits in complex natural samples such as basalts, multicomponent evaporite systems, and soils.

....Energy­-Dispersive Mode: Focus on Characteristic Cobalt Radiation

The CCD-224 directly detects individual X-ray photons that are absorbed by the active silicon, producing a number of electron hole pairs equal to the energy of the X-ray in electron volts, divided by 3.65 (the energy of an electron-hole pair in the silicon lattice). For example, a cobalt K-alpha X-ray with an energy of 6.93 keV will produce 1,899 electron hole pairs. Single pixel events (those representing the absorption of a single photon into a single pixel of the CCD) are summed into a histogram of energy vs. number of counts. This histogram constitutes the energy-dispersive fluorescence spectrum of the sample. The table shows the energy range and resolution....

Modes of X­-ray Photon Detection for X­-ray Diffraction

A special case of X-ray detection by the CCD is the detection of Co K-alpha or Co K-beta characteristic photons from the primary source. When Co K-alpha (or Co-beta) photons are detected, the X,Y pixel location in the CCD is identified and the corresponding X,Y location in a 600x582 counting number array is incremented by one. This process results in a diffraction image. Various strategies are used in on-board data processing to optimize the quality or quantity of diffraction data returned (e.g., "single pixel" detection, and "split pixel" detection).

An additional 600x582 array stores an image of all of the photons detected by the CCD regardless of energy. This array acts very much like a piece of photographic film, recording the XRD pattern as well as background, energy-dispersive data, and Bremsstrahlung.

[Emphasis mine]

I really don't know what the various strategies are and what is possible on-board, i.e if there is the possibility of performing something in between "single pixel" and "split pixel" detection but it sure looks like the potential to use compressive sensing. 

The "single pixel" capability is equivalent to the sum of all the smaller pixels with the same weights while the "split pixel" could correspond to the sum of only certain pixels with different or equal weights. If the "split pixel" capability were to allow for setting individual pixels with weight to 0/1 or some real numbers before  the summing then compressive sensing ought to be looked into. 

In effect, the mode of operation that could be proposed would be close to that of the single pixel camera (How does the Rice one pixel camera work ? ). Here though, the "single pixel" is really one configuration (all mirrors are in) whereas the "split pixel would allow other configuration as shown here.

Image Credit: NASA/JPL-Caltech/Malin Space Science Systems 
This image was taken by Mastcam: Left (MAST_LEFT) onboard NASA's Mars rover Curiosity on Sol 3 (2012-08-09 05:09:32 UTC) . 
Full Resolution

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.

Compressive Sensing with Local Geometric Features: Hardware and Implementation

Continuing up in the area of hardware / sensors using compressive sensing, here is a star tracker application. that we featured last year. 

Compressive Sensing with Local Geometric Features by Rishi Gupta,Piotr Indyk, Eric Price, Yaron Rachlin. The abstract reads:

We propose a framework for compressive sensing of images with local distinguishable objects, such as stars, and apply it to solve a problem in celestial navigation. Specifically, let x be an N-pixel real-valued image, consisting of a small number of local distinguishable objects plus noise. Our goal is to design an m-by-N measurement matrix A with m << N, such that we can recover an approximation to x from the measurements Ax. We construct a matrix A and recovery algorithm with the following properties: (i) if there are k objects, the number of measurements m is O((k log N)/(log k)), undercutting the best known bound of O(k log(N/k)) (ii) the matrix A is very sparse, which is important for hardware implementations of compressive sensing algorithms, and (iii) the recovery algorithm is empirically fast and runs in time polynomial in k and log(N). We also present a comprehensive study of the application of our algorithm to attitude determination, or finding one's orientation in space. Spacecraft typically use cameras to acquire an image of the sky, and then identify stars in the image to compute their orientation. Taking pictures is very expensive for small spacecraft, since camera sensors use a lot of power. Our algorithm optically compresses the image before it reaches the camera's array of pixels, reducing the number of sensors that are required.

Pretty much like the compressive sensing radar featured earlier, let us note that these implementations do not rely on simple vanilla compressive sensing.  Specific acquisition strategies and attendant algorithms are being developed. Here this is a derivative of the count-min sketch algorithm. If you recall this type of algorithm needs to be counting things that follow some pretty drastic power law ( see the excellent Probabilistic Data Structures for Web Analytics and Data Mining by Ilya Katsov and attendant figure below )

Let us see here the type of constraints that this type of hardware need to adhere to:

3.1 Current star trackers

A star tracker is essentially a digital camera, called a star camera, connected to a microprocessor. We describe various characteristics of the camera hardware and star identi cation algorithms.

3.1.1 Numbers

We first provide some numbers from [Lie02] and [WL99] to give a sense of scale. As of 2001, a typical CCD star tracker consumes 5-15W of power. A small spacecraft uses 200W of power, and a minimal one uses less than 100W, so this can be a substantial amount. A high-end star tracker can resolve approximately the same set of stars that an unaided human can on a moonless night away from all light pollution. The number of stars in a star tracker's database varies from 58 to many thousands. The camera's eld of view can vary from 2 2 degrees to 30 30 degrees, or anywhere from .01% to 4% of the sky. For comparison, the full moon is about .5 degrees across, and an adult st held at arm's length is about 10 degrees across. A CCD camera can have up to a million pixels, and the accuracy of the nal attitude is usually around .001 degrees (1 standard deviation), compared to .01 degrees for the next best sensors. The attitude is updated anywhere from 0.5 to 10 times a second.

The CCD has a single ADC located in the corner of the pixel array. A CCD array is read as follows: each pixel repeatedly transfers its charge into a neighboring pixel, so that the charge from any given pixel eventually travels a taxicab path to the ADC. Charges from di erent pixels are never combined, so there are a total of (n3) charge transfers. Since the ADC only digitizes one pixel at a time, it also takes (n2) time to read the whole array. In addition, each charge transfer leaves a fraction of the electrons behind, where 1   equals the charge transfer efficiency. The electrons in the farthest pixels undergo (n) charge transfers, and in practice it is costly to achieve < 10 5, which puts a bound on the maximum size of a CCD array [Hol98, Fos93]. Even if future technology were to allow a better charge transfer efficiency, it is worth noting that each charge transfer uses a large constant amount of power, and that the total number of charge transfers is super-linear in the number of pixels.

On the other hand, CMOS devices have an ADC built into every pixel. This solves all of the problems noted above, and adds another important feature: random access reading. In other words, we can choose to read and digitize only a subset of the pixels, and in practice, that is done, saving power and subsequent digital processing costs [Lie02]. However, the ADCs take up valuable real estate, and reduce the percentage of the chip that is available to collect photons. CMOS devices also generate substantially more noise than CCDs, further reducing the signal to noise ratio [Lit01].

In practice, many consumer products such as cell phone cameras use CMOS, while scienti c instruments use CCDs. Nevertheless, star trackers on small or low-power-budget satellites are starting to use CMOS, forgoing factors of 10 and higher in precision. We give the speci cation of a CCD tracker and a CMOS tracker in current (2011) production to illustrate the di erence, as well as some of the numbers in highlighted in Section 3.1.1. The CT-602 Star Tracker has a CCD camera and is made by Ball Aerospace & Technologies. It uses 8-9W of power, weighs 5.5kg, has 6000 stars in its database, an 8 8 degree eld of view, 512 512 pixels, an attitude accuracy of .0008 degrees, and updates 10 times a second [Bal]. Comtech AeroAstro's Miniature Star Tracker has a CMOS camera, uses < 2W of power, weighs .4-.8 kg, has 1200 stars in its database, a 24 30 degree field of view, and 1024 1280 pixels, but has an accuracy of only .03 degrees and updates only 2 times a second [Com].

and at the end:

The first observation we make is that ADUAF works very well down to an almost minimal number of measurements. The product p01p02 has to be greater than 800, and the minimal set of primes is 26 and 31. As the number of measurements increases, SSMP catches up and surpasses ADUAF, but we note that running SSMP (implemented in C) takes 2.4 seconds per trial on a 2.3 GHz laptop, while ADUAF (implemented in Octave/Matlab) takes .03 seconds per trial. Computation power on a satellite is substantially lower than that of a low end laptop, and given that the entire acquisition has to happen in .1 to 2 seconds, it seems unlikely that any algorithm linear or near linear in N is going to be practical. Finally, we note that the plot lines for both SSMP and ADUAF could be improved by a more sophisticated implementation of the star identi cation algorithm.

I note that the potential hardware implementation

is very similar to an idea we began to implement for a star tracker for the GIFTS program (which eventually got cancelled). There we used two field of views that we had to deconvolute.

The attendant code is here. The Smithsonian astrophysical observatory star catalog is available at http://heasarc.gsfc.nasa.gov/W3Browse/star-catalog/sao.html.

Talking about star trackers, you probably recall this magnificient shot from Hayabusa using its star tracker to image Earth and the Moon

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 Sub-Nyquist Radar Prototype: Hardware and Algorithms

Yonina just sent me the following:

Hi Igor,

I hope all is well by you.

When we met in France I told you I would let you know when we have more hardware – well, the time has come …We just had a demo of new sub-Nyquist hardware we developed for radar; you can find the details in http://arxiv.org/abs/1208.2515

Best,

Yonina

Thanks Yonina for the update.

A Sub-Nyquist Radar Prototype: Hardware and Algorithms by Eliahu Baransky, Gal Itzhak, Idan Shmuel, Noam Wagner, Eli Shoshan, Yonina C. Eldar. The abstract reads:

Traditional radar sensing typically involves matched filtering between the received signal and the shape of the transmitted pulse. Under the confinement of classic sampling theorem this requires that the received signals must first be sampled at twice the baseband bandwidth, in order to avoid aliasing. The growing demands for target distinction capability and spatial resolution imply significant growth in the bandwidth of the transmitted pulse. Thus, correlation based radar systems require high sampling rates, and with the large amounts of data sampled also necessitate vast memory capacity. In addition, real-time processing of the data typically results in high power consumption. Recently, new approaches for radar sensing and detection were introduced, based on the Finite Rate of Innovation and Xampling frameworks. These techniques allow significant reduction in sampling rate, implying potential power savings, while maintaining the system's detection capabilities at high enough SNR. Here we present for the first time a design and implementation of a Xampling-based hardware prototype that allows sampling of radar signals at rates much lower than Nyquist. We demonstrate by real-time analog experiments that our system is able to maintain reasonable detection capabilities, while sampling radar signals that require sampling at a rate of about 30MHz at a total rate of 1Mhz.

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 Invention of Compressive Sensing and Recent Results

I recently stumbled upon and loved this presentation by Yoram Bresler entitled The Invention of Compressive Sensing and Recent Results: - From Spectrum-Blind Sampling and Image Compression on the Fly to New Solutions with Realistic Performance Guarantees

I very much liked part 1 which ought to be added to the current historical record that I have seen so far (mostly Geophysics in the 1960s and so on). I also think another part of the story is not told in the realm of compressive imaging such as the hardware development by David Brady and others. Here are some "morceaux choisis"

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.

Sparsity Averaging for Compressive Imaging and Reweighted sparse deconvolution for high angular resolution diffusion MRI

Another way to look at structured sparsity is to evaluate reconstruction through several basis. This is what Yves Wiaux et al do in the first paper mentioned today with an analysis slant. Yves sent me the following:

Hi Igor,

You've certainly seen my two tweets

New article "Sparsity Averaging for Compressive Imaging" accessible at http://infoscience.epfl.ch/record/180382?ln=en ... and tomorrow on ArXiv.

New article submitted to Neuroimage on "Reweighted sparse deconvolution for high angular resolution diffusion MRI" available at: http://arxiv.org/abs/1208.2247 .

May I ask you to list those papers and abstract on nuit blanche?....

thanks

cheers

Yves

Thanks Yves. 

Here are the papers: Sparsity Averaging for Compressive Imaging by Carrillo, Rafael; McEwen, Jason; Van De Ville, Dimitri; Thiran, Jean-Philippe;Wiaux, Yves. The abstract reads:

We propose a novel regularization method for sparse image reconstruction from compressive measurements. The approach relies on the conjecture that natural images exhibit strong average sparsity over multiple coherent frames. The associated reconstruction algorithm, based on an analysis prior and a reweighted ℓ1 scheme, is dubbed Sparsity Averaging Reweighted Analysis (SARA). We test our prior and the associated algorithm through extensive numerical simulations for spread spectrum and Gaussian acquisition schemes suggested by the recent theory of compressed sensing with coherent and redundant dictionaries. Our results show that average sparsity outperforms state-of-the-art priors that promote sparsity in a single orthonormal basis or redundant frame, or that promote gradient sparsity. We also illustrate the performance of SARA in the context of Fourier imaging, for particular applications in astronomy and medicine.

Yves tells me the SARA should be available soon. Stay tuned.

Reweighted sparse deconvolution for high angular resolution diffusion MRI by Alessandro Daducci, Dimitri Van De Ville, Jean-Philippe Thiran, Yves Wiaux. The abstract reads:

Diffusion MRI is a well established imaging modality providing a powerful and innovative way to non-invasively probe the structure of the white matter. Despite the potential of the technique, the intrinsic long scan times of these sequences have hampered their use in clinical practice. For this reason, a wide variety of methods have been proposed recently with the aim to shorten acquisition times. Among them, spherical deconvolution approaches have gained a lot of interest for their ability to reliably recover the intra-voxel fiber configuration with a relatively small number of data samples. To overcome the intrinsic instabilities in solving the deconvolution problem, these methods make use of regularization schemes generally based on the assumption that the fiber orientation distribution (FOD) to be recovered is sparse, either explicitly or implicitly. In particular, convex optimization methods have recently been advocated in a compressed sensing perspective for FOD reconstruction from accelerated acquisitions. In this paper, we propose to exploit further the versatility of this powerful framework with the aim to exploit sparsity more optimally. We define a new convex minimization problem for FOD reconstruction through a constrained formulation between sparsity prior and data, also making use of a reweighting scheme. The method has been tested on both synthetic and real data. Experimental results indicate that this approach provides more robust and accurate estimates than the state of the art in terms of both the number and orientation of fiber compartments in each voxel.

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 cookies for you at the University of Wisconsin-Madison

I imagine this person behind the scene who is in charge of funding cookies to attract people to talks. He decides at the beginning of the year which of the speaker gets cookies. Unfortunately, if you went to Felix Hermann's talk Friday morning at University of Wiscosin-Madison, there was no cookies for you.

I take it as a sign of quality, the better the talk, the less the need to attract students with cookies.


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.