Thursday, May 19, 2011

Predicting Earthquakes: Is Compressive Sensing Useful ?

Prompted by Laurent Jacques's tweet, I went to read the excellent arxiv blog entry featuring a paper purporting to explain how ionospheric disturbances correlated to the Tohoku earthquake in Japan. Here are a few observations. The paper looks at three means of getting some information around the Tokohu region at about the time of the earthquake. The authors first used multispectral (AVHRR) data. This reminded me that we submitted a proposal to the NSF a while back to fly a CASSI hyperspectral sensor on board a cubesat. The proposal did not fare well and it was all my fault but maybe I should have pushed this one again last year. On the other hand, our implementation did not look at long wave IR wavelength and more importantly once you have a satellite with the right sensor, you really only have a point-like coverage of earth and there is chance you might miss some events. The next best thing is to probably to consider what you can get from a sensor network in order to improve coverage. The authors of the paper did just that by looking at ionospheric measurements. If you recall these can be done directly using the GPS constellation as explained in this Wondering Star entry. From the paper:
"...GPS TEC in the form of Global Ionosphere Maps (GIM) maps, ionospheric tomography, using the signal from low-Earth orbiting satellites (COSMOS), and data from the ground based vertical sounding network in Japan. The period of this earthquake was very environmentally noisy for our analysis since two (small and moderate) geomagnetic storms took place on the first and eleventh of March respectively (Fig 4B). There was a short period of quiet geomagnetic activity between March fifth and tenth but it was during a period of increasing solar activity. During period from 26 February through 8 March the solar F10.7 radio flux increased almost two-fold (from 88 to 155). So the identification of the ionospheric precursor was the search a signal in this noise.  .."

The Global Ionosphere Maps is updated here every five minutes ( I added a new entry on Wondering Star about this Earth-wide sensor network) but the main problem was delineating the disruption to the ionosphere due to solar storms and that due to the earthquake releasing gases into the atmosphere. Check Ionospheric Precursors of Earthquakes; Recent Advances in Theory and Practical Applications  by Sergey Pulinets for an explanation. This use of the ionosphere also reminded me of Lianlin Li's comments a while back on "the ionosphere can be looked as the natural compressive sensing measurement system". Finally, I also note that one of the commenter on the arxiv blog makes the astute comment about Bright Orange Eerie Sunsets. Maybe we ought to have a closer look at using a worldwide outdoor webcam system ? or make sense out of outdoor photos taken by a billion smartphones.

Here is the paper: Atmosphere-Ionosphere Response to the M9 Tohoku Earthquake Revealed by Joined Satellite and Ground Observations. Preliminary results by Dimitar Ouzounov, Sergey Pulinets, Alexey Romanov, Alexander Romanov, Konstantin Tsybulya, Dimitri Davidenko, Menas Kafatos, Patrick Taylor. The abstract reads:
The recent M9 Tohoku Japan earthquake of March 11, 2011 was the largest recorded earthquake ever to hit this nation. We retrospectively analyzed the temporal and spatial variations of four different physical parameters - outgoing long wave radiation (OLR), GPS/TEC, Low-Earth orbit tomography and critical frequency foF2. These changes characterize the state of the atmosphere and ionosphere several days before the onset of this earthquake. Our first results show that on March 8th a rapid increase of emitted infrared radiation was observed from the satellite data and an anomaly developed near the epicenter. The GPS/TEC data indicate an increase and variation in electron density reaching a maximum value on March 8. Starting on this day in the lower ionospheric there was also confirmed an abnormal TEC variation over the epicenter. From March 3-11 a large increase in electron concentration was recorded at all four Japanese ground based ionosondes, which return to normal after the main earthquake. We found a positive correlation between the atmospheric and ionospheric anomalies and the Tohoku earthquake. This study may lead to a better understanding of the response of the atmosphere /ionosphere to the Great Tohoku earthquake

Wednesday, May 18, 2011

It's full of stars and everything in between.

How fitting for the last launch of Endeavor that will put the AMS in orbit. Six months ago, I wondered when compressed sensing would be used in the context of weak lensing. A month ago, I then wondered how we could estimate the mass of the universe using similar techniques. Well, it looks like some folks have been wondering the same thing for a long time now. In particular, Adrienne Leonard will present the following work at Texas A&M next week:

Title: Compressed Sensing for Weak Lensing
Abstract:
Weak gravitational lensing allows us to map the distribution of matter in the universe by measuring the small distortions to galaxy images arising due to the gravitational potential along the line of sight. The measured shear is effectively a convolution of the matter overdensity with a broad radial kernel encoding geometrical information. Therefore, the weak lensing problem can be modeled as an instance of compressed sensing, as we know that the matter overdensity is mostly sparse in some wavelets domains. In this case, the sensing operator models an integration along each line of sight, from low redshift (i.e. close distance) to high redshift (i.e. far away distance). Then, we exploit current results on the compress sensing theory in order to build an efficient method for estimating the matter density along lines of sight using most of the theoretical knowledge available. More precisely, the reconstruction problem is cast as a constraints convex optimization problem, where we seek a sparse solution under data fidelity constraints. We also characterize the solution and prove the convergence of the global scheme. The results show that we are able to reconstruct the matter cluster in different redshifts without the smooth and shift issues that occur in the current state-of-art methods.

I can't wait to see the paper and/or presentation.

Credit: NASA

CS: Group sparse based CS for dynamic MRI

Muhammad Usman mentioned to me the following two "abstracts" recently presented at ISMRM 2011:

Over the last few years, the combination of Compressed sensing (CS) and parallel imaging have been of great interest to accelerate MRI. For dynamic MRI, K-t sparse SENSE (K-t SS) has been proposed [1] for combining the CS based K-t Sparse method [2] with SENSE. Recently, K-t group sparse method (K-t GS) [3] has been shown to outperform K-t Sparse for single coil reconstruction, by exploiting the sparsity and the structure within the sparse representation (x-f space) of dynamic MRI. In this work, we propose to extend K-t GS to parallel imaging acquisition in order to achieve higher acceleration factors by exploiting the spatial sensitive encoding from multiple coils. This approach has been called K-t group Sparse SENSE (K-t GSS). In contrast with the previous single-coil based K-t GS method for which a performance parameter is manually optimized for every frequency encode; we propose an entropy based scheme for automatic selection of this parameter. Results from retrospectively undersampled cardiac gated data show that K-t GSS outperformed K-t sparse SENSE at high acceleration factors (up to 16 fold).

Over the last years, Compressed Sensing has been of great interest to accelerate dynamic MRI [1-4]. The recently introduced k-t Group Sparse (k-t GS) method [4] exploits not just the sparsity of dynamic MRI but also the spatial group structure of its sparse representation (x-f space). The reconstruction is done by solving a mixed L1-L2 norm minimization that enforces sparsity in the group selection. K-t GS achieves higher acceleration factors compared to the conventional k-t Sparse method [1-2]. However, it presents two drawbacks: a) an additional training scan is required to assign the groups in x-f space, and b) the group assignment is based only on the connectivity of neighbouring pixels using a time consuming hard thresholding scheme. In this work we propose to modify k-t GS by using the sorted intensity of the sparse representation, estimated from the same acquired data, for group assignment. With this approach groups are assigned by clustering the expected intensity distribution of the x-f space and not the spatial structure of the x-f space as in k-t GS. We have called this approach k-t Group Sparse using Intensity based clustering (k-t GSI) and it has been tested in cine and perfusion cardiac images.


Credit NASA, the last launch of Endeavor (STS-134)

Tuesday, May 17, 2011

Algorithms In The Field (#8f)

From David Eppstein's summary of day one of the Algorithm In The Field NSF workshop:

...Graham Cormode had a nice survey of data sketching algorithms, which he represented as a haiku that I unfortunately failed to copy down. But basically he's interested in methods that have some properties among: sublinear storage, randomized, linear, can be added together; they include methods such as Bloom filters, minhashing (for which he described a nice variation that estimates the number of distinct items in a set with good multiplicative error), and the count-min sketch (which gives an additive approximation to the frequency of each item in a data stream). Towards the end he listed situations in which these methods are actually used "in the field": he included web log analysis and compressed sensing, and explicitly excluded sensor networks because the theoretical applications of sketching in sensor networks as huge randomly placed networks with too much data to store do not match the scientific applications of at most a dozen or two carefully placed sensors from which one wants to collect all the raw data. He also listed quite a few potential applications, but I think he could have included a lot more real applications if he had included Bloom filters in his application section as he did in his historical survey....

CS: Heuristics for Rank Proxy and how it changes everything....


Work is steadily expanding from compressive sensing into low rank matrix decomposition and showing up on different approaches such as the ones dealing with time issues ( Low Rank and Compressive Imaging by Gonzalo Arce's group ) but they are not the only ones.  Recently, for instance, I mentioned the work on sub-wavelength imaging via quadratic compressive sensing at the Technion. Surely enough, this type of approach is really going beyond traditional signal processing and it requires us to learn new things.

As an aside, while the heuristics of the nuclear norm (replacing the rank functional) seems to have gotten a lot of interest in the recent algorithm development work, one should also remember that this is not the only one as shown in the recent Quadratic Compressive Sensing work and more pointedly in this 2003 paper entitled: Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices by Maryam Fazell, Haitham Hindi, Stephen P. Boyd. I asked Yonina Eldar why they used the log-det heuristics (using CVX), and she responded that it worked better than the nuclear norm proxy. So as one can see, it looks like we are going to have a rich set of solvers in the next upcoming years, aren't we lucky, uh ? As it turns out, today we have four papers using nuclear norm heuristics to deal  with time dependent MRI and Computed Tomography. Enjoy!

In recent years, there has been a concerted effort to reduce the MR scan time. Signal processing research aims at reducing the scan time by acquiring less K-space data. The image is reconstructed from the subsampled K-space data by employing compressed sensing (CS)-based reconstruction techniques. In this article, we propose an alternative approach to CS-based reconstruction. The proposed approach exploits the rank deficiency of the MR images to reconstruct the image. This requires minimizing the rank of the image matrix subject to data constraints, which is unfortunately a nondeterministic polynomial time (NP) hard problem. Therefore we propose to replace the NP hard rank minimization problem by its nonconvex surrogate — Schatten p-norm minimization. The same approach can be used for denoising MR images as well. Since there is no algorithm to solve the Schatten p-norm minimization problem, we derive an efficient first-order algorithm. Experiments on MR brain scans show that the reconstruction and denoising accuracy from our method is at par with that of CS-based methods. Our proposed method is considerably faster than CS-based methods

Accelerating multi-echo T2 weighted MR imaging: Analysis prior group-sparse optimization by Angshul Majumdar, Rabab K. Ward. The abstract reads:
This works addresses the problem of reconstructing multi-echo T2 weighted MR images from partially sampled K-space data. Previous studies in reconstructing MR images from partial samples of the K-space used Compressed Sensing (CS) techniques to exploit the spatial correlation of the images (leading to sparsity in transform domain). Such techniques can be employed to reconstruct the individual T2 weighted images. However, in the current context, the different images are not independent; they are images of the same cross section, and hence are highly correlated. In this work, we not only exploit the spatial correlation within the image, but also the correlation between the images to achieve even better reconstruction results.
For individual MR images, CS based techniques lead to a sparsity promoting optimization problem in a transform domain. In this paper, we show how to extend the same framework in order to incorporate correlation between images leading to group sparsity promoting optimization. Group sparsity promoting optimization is popularly formulated as a synthesis prior problem. The synthesis prior formulation for group sparsity leads to superior reconstruction results compared to ordinary sparse reconstruction. However, in this paper we show that when group sparsity is framed as an analysis prior problem the reconstruction results are even better for proper choice of the sparsifying transform. An interesting observation of this work is that when the same sampling pattern is used to sample the K-space for all the T2 weighted echoes, group sparsity does not yield any noticeable improvement, but when different sampling patterns are used for different echoes, our proposed group sparsity promoting formulation yields significant improvement (in terms of Normalized Mean Squared Error) over previous CS based techniques.

This works addresses the problem of reconstructing multiple T1- or T2-weighted images of the same anatomical cross section from partially sampled K-space data. Previous studies in reconstructing magnetic resonance (MR) images from partial samples of the K-space used compressed sensing (CS) techniques to exploit the spatial correlation of the images (leading to sparsity in wavelet domain). Such techniques can be employed to reconstruct the individual T1- or T2-weighted images. However, in the current context, the different images are not really independent; they are images of the same cross section and, hence, are highly correlated. We exploit the correlation between the images, along with the spatial correlation within the images to achieve better reconstruction results than exploiting spatial correlation only. For individual MR images, CS-based techniques lead to a sparsity-promoting optimization problem in the wavelet domain. In this article, we show that the same framework can be extended to incorporate correlation between images leading to group/row sparsity-promoting optimization. Algorithms for solving such optimization problems have already been developed in the CS literature. We show that significant improvement in reconstruction accuracy can be achieved by considering the correlation between different T1- and T2-weighted images. If the reconstruction accuracy is considered to be constant, our proposed group sparse formulation can yield the same result with 33% less K-space samples compared with simple sparsity-promoting reconstruction. Moreover, the reconstruction time by our proposed method is about two to four times less than the previous method.


The purpose of this article for four-dimensional (4D) computed tomography (CT) is threefold. (1) A new spatiotemporal model is presented from matrix perspective with the row dimension in space and the column dimension in time, namely, Robust PCA based 4DCT model (Robust Principle Component Analysis based 4D CT). That is, instead of viewing the 4D object as a temporal collection of three-dimensional (3D) images and looking for local coherence in time or space independently, we perceive it as a mixture of low-rank matrix and sparse matrix to explore the maximum temporal coherence of spatial structure among phases. Here the low-rank matrix corresponds to the “background” or reference state, which is stationary over time or similar in structure; the sparse matrix stands for the “motion” or time-varying component, e.g., heart motion in cardiac imaging, which is often either approximately sparse itself or can be sparsified in the proper basis. Besides 4D CT, this Robust PCA based 4DCT model should be applicable in other imaging problems for motion reduction or/and change detection with the least amount of data, such as multi-energy CT, cardiac MRI, and hyperspectral imaging. (2) A dynamic strategy for data acquisition, i.e., a temporally spiral scheme, is proposed that can potentially maintain the similar reconstruction accuracy with much fewer projections of the data. The key point of this dynamic scheme is to reduce the total number of measurements and hence the radiation dose, by acquiring complementary data in different phases while reducing redundant measurements of the common background structure. (3) An accurate, efficient, yet simple-to-implement algorithm based on split Bregman method is developed for solving the model problem with the sparse representation in tight frames.

Monday, May 16, 2011

A 35 year tale

Beyond the extraordinary will behind this project, I also note the change in the quality of the movies over the years.





Via PetaPixel

Leveraging a conference


While following the #8f hashtag on twitter is nice, it really is a little short. If you are organizing a conference like the one listed here (and below) that having a video in the room will multiply your audience by a hundred. Your sponsors want to know that. The table above show the statistics of a recent series of talks in Cambridge, I have watched this statistics evolve over time and the ratio of a hundred times more people watching the videos outside the university than inside, has been pretty constant.

I Am Nothing To You

Every once in a while I am being asked to feature a paper that the author kindly sends along as an E-mail attachment. It's either an accepted for publication preprint or an already published paper, either way, our community has already paid through the review process it took to make that final version. People reading this blog are generally part of that community, they will think highly of you not because your paper is featured here but because the insight you provide is going to change their world. What is the point of sending me a copy of that paper for my own use ? I don't write your paycheck, I certainly don't give you a job and I almost certainly am not the right person to say whether what you wrote is worth a damn. In short,  I am nothing to you. You want to be a rock star, act like one.

Credit: Robert Pless, AMOS picture of the day. Can you explain the colors

Sunday, May 15, 2011

NSF Workshop: 8F (Algorithms in the field)

The Algorithms in the field NSF workshop is starting tomorrow (hashtag is #8f on Twitter). Suresh invites us to "...make your opinions known. But even if you're not, you can voice them right here ! I'll incorporate comments posted here into the discussions (and sign your name if you'd like credit)." Muthu also mentions it here. Here is the current list of talks:


Recommender Systems: The Art and Science of Matching Items to Users

Speaker: Deepak Agarwal

Yahoo! Research
Algorithmically matching items to users in a given context is essential for the success and profitability of large scale recommender systems like content optimization, computational advertising, search, shopping, movie recommendation, and many more. The objective is to maximize some utility (e.g. total revenue, total engagement) of  interest over a long time horizon, hence this is a bandit problem since there is positive utility in displaying items that may have low mean but high variance. A key challenge in such bandit problems is the curse of dimensionality --- data is obtained via interactions among several heavy-tailed categorical variables and the goal is to estimate response rates of some rare event like click, buy, and so on.  Other than statistical challenges due to high dimensionality and data sparsity,  bandit problems are difficult to work with for response that are observed with considerable delay (e.g. return visits, confirmation of a buy). To mitigate this issue, one approach is to optimize multiple competing objectives in the short-term to achieve the best long-term performance. For instance, in serving content to users on a website, one may want to optimize some combination of clicks and downstream advertising revenue in the short-term to maximize revenue in the long-run. This combination of bandits, high dimensional modeling, and constrained optimization in an environment where one has access to a persistent stream of data arriving at high frequency, poses unique algorithmic challenges. In this talk, I will attempt to capture some of the technical issues by focusing on a concrete application - content optimization on the Yahoo! front page. I will briefly discuss our own research, mention some specific open problems, and outline some broad technical challenges in this area.
About the speaker: Deepak Agarwal is a statistician at Yahoo! who is interested in developing statistical and machine learning methods to enhance the performance of large scale recommender systems. Deepak and his collaborators significantly improved article recommendation on several Yahoo! websites, most notably on the Yahoo! front page. He also works closely with teams in computational advertising to deploy elaborate statistical models on the RightMedia Ad Exchange, yet another large scale recommender system. He currently serves as associate editor for the Journal of American Statistical Association.

Sampling-Based Motion Planning: From Intelligent CAD to Group Behaviors to Protein Folding
Nancy Amato

Department of Computer Science and Engineering
Texas A&M University
Motion planning arises in many application domains such as computer animation (digital actors), mixed reality systems and intelligent CAD (virtual prototyping and training), and even computational biology and chemistry (protein folding and drug design). Surprisingly, a single class of planners, called sampling-based planners, have proven effective on problems from all these domains. In addition to versatility, these methods are simple and efficient, even in high-dimensional configuration spaces.
In this talk, we describe two major classes of sampling-based planners, the graph-based probabilistic roadmap method (PRM) and the tree-based rapidly-exploring random tree (RRT). We give an overview of some PRM variants developed in our group and present work related to virtual prototyping, multi-agent systems, and protein folding. For virtual prototyping, we show that in some cases a hybrid system incorporating both an automatic planner and haptic user input leads to superior results. For multi-agent systems, we describe PRM-based techniques for herding, pursuit/evasion and evacuation planning. Finally, we describe our application of PRMs to simulate molecular motions, such as protein and RNA folding. More information regarding our work, including movies, can be found at http://parasol.tamu.edu/~amato/
Bio: Nancy M. Amato is a professor of computer science and engineering at Texas A&M University where she co-directs the Parasol Lab, is Deputy Director of the Institute for Applied Math and Computional Science, is past chair of the Council of Principal Investigators and chair of the Alliance for Bioinformatics, Computational Biology, and Systems Biology. She received undergraduate degrees in Mathematical  Sciences and Economics from Stanford University, and masters and Ph.D.  degrees in Computer Science from UC Berkeley and UIUC. She received an NSF CAREER Award, is an IEEE Fellow, is an ACM Distinguished Speaker, and was a Distinguished Lecturer for the IEEE Robotics and Automation Society.  She was an Associate Editor of the IEEE Transactions on Robotics and  Automation and the IEEE Transactions on Parallel and Distributed Systems.  She is a member of the Computing Research Association's Committee on the  Status of Women in Computing Research (CRA-W) and of the Coalition to  Diversity Computing (CDC); she co-directs the CDC/CRA-W Distributed Research  Experiences for Undergraduates (DREU) program and the CDC/CRA-W Distinguished  Lecture Series. She is Co-Chair of the NCWIT Academic Alliance. Her main areas  of research focus are motion planning and robotics, computational biology and geometry, and parallel and distributed computing

Optimization Challenges in Machine Learning and Data Mining
Kristin P. Bennett

Rensselaer Polytechnic Institute
The areas of machine learning and mathematical programming are increasingly intertwined. Optimization problems lie at the heart of most machine learning approaches. Machine learning researchers have embraced the advances in convex mathematical programming contributing to rapid advances in machine learning models and algorithms. In turn, the particular nature of machine learning models has stimulated new advances in convex optimization. Recently, nonsmooth optimization methods have led to massively scalable algorithms for solution of convex machine learning models such as Support Vector Machines. However convex machine learning models are not enough. Using problems in drug discovery, we will illustrate how nonconvex models can elegant capture learning tasks and how novel nonsmooth nonconvex optimization methods can be analogously used to create scalable algorithms for solving these nonconvex machine learning models. Advances in nonsmooth and nonconvex optimization theory and algorithms to meet the challenges of machine learning and data mining could contribute to another surge of synergistic advances in both learning and mathematical programming with far reaching impact in many domains.

Scalable Topic Modeling
David Blei

Princeton Univ
Probabilistic topic modeling provides a suite of tools for the unsupervised analysis of large collections of documents. Topic modeling algorithms can uncover the underlying themes of a collection and decompose its documents according to those themes. This analysis can be used for corpus exploration, document search, and a variety of prediction problems.
In this talk, I will review the state-of-the-art in probabilistic topic models. I will describe the ideas behind latent Dirichlet allocation and its extensions, and I'll point to some of the software
available for topic modeling.
I will then describe our online strategy for fitting topic models, which lets us analyze massive document collections and document collections arriving in a stream. Our algorithm can fit models to millions of articles in a matter of hours, and I will present a study of 3.3M articles from Wikipedia. These results show that the online approach finds topic models that are as good as or better than those found with traditional inference algorithms.
(Joint work with Matthew Hoffman, Francis Bach, and Chong Wang)

Some Sketchy Results
Graham Cormode

At&T Labs - Research
'Sketch' data structures are simple, efficient, compact summaries of large data sets.  Sketches enable approximate computations like similarity comparison and summarization of distributions. There have been a number of successes where use of sketches have been applied in the field, most notably when dealing with very large data sets.  In this talk, I'll present some key sketches and their properties, and describe some successes and some non-successes in their application.  I'll conclude by outlining emerging applications for sketches, and their future potential.

Scaling data mining techniques
Anirban Dasgupta

Yahoo! Research
In this talk, we will discuss problems that arise from scaling data mining and machine learning techniques for large, sparse, high dimensional datasets. We will discuss this in the context of two theoretical constructs -- random projection and locality sensitive hashing. Random projection has been much studied as a primitive in various algorithms to control dependence on input dimension. We will show a machine learning application that motivates, in addition, the preservation of sparsity of input vectors, and show a corresponding new construction. We will also discuss improvements to locality sensitive hashing techniques that enable a theoretically justifiable, and empirically observed lift in performance.

Minimizing Communication in Linear Algebra
Jim Demmel

UC, Berkeley
Algorithms have two kinds of costs: arithmetic and communication, by which we mean moving data either between levels of a memory hierarchy (in the sequential case) or between processors over a network (in the parallel case). Communication costs can already exceed arithmetic costs by orders of magnitude, and the gap is growing exponentially over time following technological trends, so our goal is to design linear algebra algorithms that minimize communication. First, we show how to extend known communication lower bounds for O(n^3) dense matrix multiplication to all direct linear algebra, i.e. for solving linear  systems, least squares problems, eigenproblems and the SVD, for dense or sparse matrices, and for sequential or parallel machines. We also describe new algorithms that attain these lower bounds; some implementations attain large speed ups over conventional algorithms. Second, we show how to minimize communication in Krylov-subspace methods for solving sparse linear system and eigenproblems, and  again demonstrate new algorithms with significant speedups.

Universal laws and architectures
John Doyle

Caltech 
Essential dimensions of complex systems research are the hard limits on what is achievable (laws), the organizing principles that succeed or fail in achieving them (architectures and protocols), the resulting behavior observed in real systems (behavior, data), and the processes by which systems evolve (variation, selection, design).  Hard limits on measurement, prediction, communication, computation, decision, and control, as well as the underlying physical energy and material conversion mechanism necessary to implement these abstract processes are at the heart of modern mathematical theories of systems in engineering and science.  Unfortunately, these subjects remain largely fragmented and incompatible, even as the tradeoffs between these limits are of growing.   The principle aim of this talk is to motivate an integrated theory based on optimization and robustness.
Insights can be drawn from three converging research themes. First, detailed description of components and a growing attention to systems biology and neuroscience, the organizational principles of organisms and evolution are becoming increasingly apparent.  While the components differ and the system processes are far less integrated, advanced technology’s complexity is now approaching biology’s and there are striking convergences at the level of organization and architecture.  Determining what is essential about this convergence and what is merely historical accident  requires a deeper understanding of architecture — the most universal, high-level, persistent elements of organization — and protocols. Protocols define how diverse modules interact, and architecture defines how sets of protocols are organized. Finally, new mathematical frameworks for the study of complex networks suggests that this apparent network-level evolutionary convergence within/between biology/technology is not accidental, but follows necessarily from their universal system requirements to be fast, efficient, adaptive, evolvable, and most critically, robust to perturbations in their environment and component parts. 
 We will sketch the underlying mathematical ideas and illustrate the key results with case studies drawn from statistical mechanics, turbulence, cell biology, human physiology and medicine, wildfire ecology, earthquakes, the Internet, market volatility, toys, fashion, and neuroscience.  If there is time we will also review (i.e. poke fun at) a remarkably popular and persistent source of error and confusion, namely the many past and ongoing attempts to find “new sciences” of complex systems and networks.  This highlights another apparent tradeoff we must overcome in complex systems, between the popularity and accessibility of ideas versus their mathematical rigor and practical relevance. 


From FOCS to Sand Hill Road
Martin Farach-Colton

Rutgers Univ
In this talk, I'll be presenting the steps of a multi-phase transformation:
       1) My theory work on cache-oblivious algorithms
       2) Collaborative systems/algorithmic work on high-performance file systems and how that changed the theory I do
       3) The breakthrough that lead to my company, Tokutek
       4) What I've learned about how people use software and how that changed the theory I do
       5) What it means to do algorithms work in a wide context.


Statistical Methods and Algorithms for the Analysis of Social Network Data 
Stephen E. Fienberg 

Department of Statistics, Heinz College, and Machine Learning Department
Carnegie Mellon University
There are three broad classes of statistical models used for the analysis of (social) network data: exponential random graph models, latent space models, and mixed membership stochastic blockmodels. They have been used in both static (cross-sectional) and dynamic (longitudinal) network situations. “Exact” computation for such models often relies on iterative or simulation methods, such as Markov chain Monte Carlo methods, which do not scale especially well to large sparse network settings. For some models good approximations are available. We give an overview of the models and computational approaches for estimating their parameters. We also discuss model degeneracies that pose special problems of both computational and inferential sorts. Fast and scalable computations of network motifs have been of special interest in the machine learning literature but they do not appear to help enough for problems of model estimation and assessing model goodness-of-fit.

Reflections on Algorithm Engineering in Computer Graphics
Eugene Fiume

University of Toronto
Computer graphics is both a mathematical science and an engineering discipline.  Mathematical modelling of biological, geometric and physical phenomena are a common first step; these models then require careful transformation into simulation and control algorithms that are aware of the constraints imposed by numerical precision, large heterogeneous data requirements, and idiosyncrasies of different computing platforms, run-time systems, operating systems and languages.  In this, computer graphics is not much different from other numerically rich application areas.  The differentiation is that error and complexity measures are at best a starting point for determining a "good" implementation, for the human visual system is the final arbiter, both of image quality and of responsiveness.  I will survey some of these issues and propose that we enhance the education of our undergraduate and particularly graduate students in applied computation.

Principles of Fact and Ontology Mining from the Web
Alon Halevy

Google
The World-Wide Web can be viewed as the biggest repository of factual information available to mankind. Facts on the Web are typically embedded in text and sometimes presented in more structured form such as tables or lists. As a result, since the WWW emerged, it has been mined for knowledge bases that can be used for query answering and higher-level inference. I will describe some of the challenges we face when trying to extract knowledge bases from the Web. In particular, I will focus on two issues that emerged in our work on the WebTables Project, a collection of over 100 million tables extracted from the Web. The first issue is the need for a principled theory for assigning confidence for facts mined from the web that considers the uneven popularity of different facts on the Web (e.g., "capital of France" vs. "capital of Malawi") and limitations of the extractors we employ. The second issue is the need to develop more flexible knowledge representation mechanisms (schema languages) that can deal with the inherent uncertainty and lack of central data modeling on the Web.

Online Matching of Ads with Advertisers
Kamal Jain

MSR 
Online matching was introduced by Karp-Vazirani-Vazirani in 1990's. In the last decade the setup was used to study the problem of allocating ad slots to advertisers. Online algorithms were proposed with worst case ratio of 63% and works only for hard budgets.
One criticism of such algorithms and analysis for practical use is their pessimistic viewpoint. We suggest a flexible online algorithm. Our algorithm is flexible in many ways.
1. It allows soft budgets.
2. It allows the optimal performance to be computed on a computer.
3. It allows accommodating the known stochastic information.
4. It allows tuning the algorithm during the run time, such as making it more aggressive or conservative, depending on whether one is going luckier or unluckier than usual.
The analysis of the algorithm shows that a tight-example and an optimal algorithm are primal-dual pairs or in other words satisfy min-max relationship. In doing so we introduced a new kind of duality for convex programs and adapt the primal-dual algorithmic technique to convex programs. This technique usually result in fast combinatorial algorithms.

Cheap Wins: Applications from Elementary Algorithms
David Karger

MIT
While theoretical computer science often develops deep and rich techniques by abstracting important problems from specific application domains, there are many cases where the standard algorithmic toolbox already contains the answers to important problems.  In such cases the key contribution of the theoretician may be simply to recognize and apply the appropriate solutions.  I'll run through some examples from natural language processing, peer to peer systems, networking, coding, and computational biology.  And I'll explore the place of this kind of algorithms "service" work on our theoretical field.

Algorithms and Social Networks: How Close are our Ties?
David Kempe

USC
Social Networks have been one of the application areas that have inspired quite a lot of algorithms work lately.  This is only natural: on the one hand, they are a very tangible concept that laymen can relate to (friendships, Facebook);  on the other hand, they are naturally modeled as graphs (one of our favorite classes of objects), and give rise to novel algorithmic questions on them.
A large fraction of the work has focused on what we can do with information on social networks.  Algorithmic tasks include identifying social communities (densely connected groups of individuals),  tracking their evolution, locating influential individuals, or devising viral marketing strategies. A complementary approach views the networks themselves as executing algorithms, such as routing messages, spreading information, facilitating trades, or allocating social stature or power.
Several of these directions have shown appeal to multiple communities with different tool sets and  approaches, including theoretical computer science, physics, machine learning, and data mining.  Often, the strucutral results and algorithmic techniques are intriguing, and long sequences of papers explore ever-refined versions of the models or definitions.
At the same time, our point of departure - treating social networks simply as graphs, or perhaps graph  augmented with a simplistic dynamic of our own design - frequently creates a disconnect to the actual application area (social networks) we would like to have an impact on. I would like to argue that as a community, we should perhaps try to understand more closely what questions matter to sociologists or researchers who really deal with social networks. More importantly, we should gain more understanding of actual human behavior. This may help push our contribution from intriguing papers to impact in the field.

Enriching Education Through Data Mining
Krishnaram Kenthapadi 

MSR
Education is acknowledged to be the primary vehicle for improving the economic well-being of people. Textbooks have a direct bearing on the quality of education imparted to the students as they are the primary conduits for delivering content knowledge. They are also indispensable for fostering teacher learning and constitute a key component of the ongoing professional development of the teachers.
Many textbooks, particularly from emerging countries, lack clear and adequate coverage of important concepts.  In this talk, we present our early explorations into developing a data mining based approach for enhancing the quality of textbooks. We discuss techniques for algorithmically augmenting different sections of a book with links to selective content mined from the Web. For finding authoritative articles, we first identify the set of key concept phrases contained in a section. Using these phrases, we find web (Wikipedia) articles that represent the central concepts presented in the section and augment the section with links to them.  We also describe a framework for finding images that are most relevant to a section of the textbook, while respecting global relevancy to the entire chapter to which the section belongs. We pose this problem of matching images to sections in a textbook chapter as an optimization problem and present an efficient algorithm for solving it.
We also present a diagnostic tool for identifying those sections of a book that are not well-written and hence should be candidates for enrichment. We propose a probabilistic decision model for this purpose, which is based on syntactic complexity of the writing and the newly introduced notion of the dispersion of key concepts mentioned in the section. The model is learned using a tune set which is automatically generated in a novel way. This procedure maps sampled text book sections to the closest versions of Wikipedia articles having similar content and uses the maturity of those versions to assign need-for-enrichment labels. The maturity of a version is computed by considering the revision history of the corresponding Wikipedia article and convolving the changes in size with a smoothing filter.
We also provide the results of applying the proposed techniques to a corpus of widely-used, high school textbooks published by the National Council of Educational Research and Training (NCERT), India. We consider books from grades IXÐXII, covering four broad subject areas, namely, Sciences, Social Sciences, Commerce, and Mathematics. The preliminary results are encouraging and indicate that developing technological approaches to enhancing the quality of textbooks could be a promising direction for research for our field.

Algorithm Design using Spectral Graph Theory
Gary L Miller

Computer Science Department, Carnegie Mellon
Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is a nearly linear time solvers Symmetric Diagonally Dominate system (SDD). This seemingly restrictive class of systems has received substantial interest and in the last 15 years both algorithm design theory and practical implementations have made substantial progress.  There is also a growing number of problems that can be efficiently solved using SDD solvers including: image segmentation, image denoising, finding solutions to elliptic equations, computing maximum flow in a graph, graph sparsification, and graphics.
Theoretically, we have recently shown that if $A$ is an $nxn$ SDD matrix with $m$ entries the linear system $Ax =b$ can be solve to constant precision in $O(m \log n)$ time ignoring lower order factors. On the implementation side, the latest code runs in linear time experimentally for large sparse systems.  In fact the problem sizes are now large enough that on modern multicore workstations the memory bandwidth is a limiting factor.  Compression techniques are now used to substantially speedup the solver.
This represents joint work with: Guy Blelloch,  Ioannis Koutis,  Richard Pang,  Kanat Tangwongsan,
and David Tolliver

Algorithmic Aspects of Real-Time System Design
Aloysius K. Mok

Department of Computer Science, University of Texas at Austin
Real-time systems have timeliness properties that must be satisfied. Because the real-time behavior of programs depends on implementation details, the traditional software design approach that abstracts away implementation details and focuses on functional correctness does not work well for real-time system design. To address this issue, we describe an annotation scheme that is used to superimpose timeliness assertions on top of the functional specification of programs. The first part of this talk will discuss some formal aspects of the annotation scheme, including the logical basis, the algorithmic analysis and synthesis problems and the related issues such as implementability and robustness in real-time scheduler design.
The second part of this talk will address the design problems of real-time systems in an open system environment. In the open system environment, a set of resources is shared by multiple applications each of which has its own resource scheduling policy, and the resource scheduling policy of each individual application is not accessible by other applications. Because of the resource scheduler isolation, meeting the timeliness requirements requires new resource sharing models and analysis techniques. We shall discuss the concept of real-time resource virtualization and the related resource allocation problems. If time permits, we shall touch on real-time database issues and speculate about real-time intelligent agent design.

It pays to do the right thing: Incentive mechanisms for Societal Networks
Balaji Prabhakar

Stanford University
Why did kamikaze pilots wear helmets?
Why does glue not stick to the inside of the bottle?
Why is lemonade made with artificial flavor but dishwashing liquid made with real lemons?
How can I avoid traffic jams and be paid for it?
While the first three are some of life's enduring questions, the fourth is the subject of decongestion research projects at Stanford University and in Singapore.  In this talk, I will briefly describe these projects and, more generally, discuss incentive mechanisms for Societal Networks; for example, transportation, energy, healthcare and waste management networks. I will talk about incentive mechanisms and experiments for reducing road congestion, pollution and energy use, and for improving "wellness" and good driving habits.  Some salient themes are: using low-cost sensing technology to make Societal Networks much more efficient, using price as a signal to co-ordinate individual behavior, and intelligently "throwing money at problems".

Insights into Routing in Real-world Networks
D. Sivakumar

Yahoo! Research
Sociologist Stanley Milgram's experiments on the "small-world" phenomenon have led to a variety of fascinating questions at the intersection of sociology and computer science.  In this work, we seek to understand what makes routing algorithms similar to those employed by Milgram work as effectively as they do.  To this end, we develop a network models and tools, and provide theoretical and empirical answers this question. While affirming the importance of the role of weak ties (as pioneered by Granovetter in sociology and modeled crisply by Kleinberg in CS), our work highlights the role of two phenomena -- the existence of a dual space of affiliations of the members of the network, and the emergence of central nodes in the network.

Dealing with Massive Data: Parallelism to the Rescue
Sergei Vassilvitskii 

Yahoo! Research
The present availability of data has lead to data analysis problems whose size would be unimaginable just 10 years ago. With datasets routinely measured in gigabytes and terabytes, one challenge that has emerged is scaling algorithms to  handle this deluge of information. With chip designers sustaining Moore’s law by turning to parallelism, so have algorithmicists turned to parallelism to speed up algorithms and improve performance. In this talk, we will focus on the MapReduce model of parallel computing, highlight some of the recent algorithmic advances and present current challenges. 

Slowly but surely they'll join our side of the Force...

Back in February 2009, Jack Dongarra, the father of LinPack/LAPACK, sent this request to the NA-Digest Mailing list:

Subject: Linear algebra software survey request
We are planning to update the survey of freely available software for the solution of linear algebra problems. The September 2006 version of the survey can be found at: http://www.netlib.org/utk/people/JackDongarra/la-sw.html. The aim is to put in “one place” the source code that is freely available for solving problems in numerical linear algebra, specifically dense, sparse direct and iterative systems and sparse iterative eigenvalue problems. Please send me updates and corrections. I will post a note on the na-digest when the new list is available.
Thanks,
Jack 

To which, I naively replied with:

Dear Dr. Dongarra,
In a recent NA-Digest you proposed to update the Linear algebra software survey. I was wondering how you were viewing the solvers currently being developed by the folks in the compressive sensing literature. As you know, the problems being solved are underdetermined linear problems and the solvers are nonlinear solvers. A set of examples/links to actual implementation (mostly in matlab) can be found here:
Would these solvers fit into the survey ?....

To which Jack kindly replied with:
Igor,
Its a bit too far afield.
Regards,
Jack

Fast forward two years later, what wasn't my surprise when I saw the following on my radar screen:

We show in this paper how linear algebra calculations can be enhanced by statistical techniques in the case of a square linear system Ax = b. We study a random transformation of A that enables us to avoid pivoting and then to reduce the amount of communication. Numerical experiments show that this randomization can be performed at a very aff ordable computational price while providing us with a satisfying accuracy when compared to partial pivoting. This random transformation called Partial Random Butter y Transformation (PRBT) is optimized in terms of data storage and ops count. We propose a solver where PRBT and the LU factorization with no pivoting take advantage of the latest generation of hybrid multicore/GPU machines and we compare its G op/s performance with a solver implemented in a current parallel library


So when are we starting Random Projection LAPACK or RP-LAPACK ?

Printfriendly