Parlor Games, Compressive Sensing, Data Analytics . . . & small BIG Data?

Parlor Game . . .

Surely, you have been part of a “guessing game” at a dinner party. Someone says, “Think of 10 numbers and tell me their sum and then tell me 2 of the 10 numbers; I will tell you the other 8 numbers you thought of”. The general reaction will be that this person is crazy! Too many unknowns, not enough constraints, too many solutions and so on.

Compressive Sensing:

There is a tsunami of activity in mathematical circles these days related to the parlor guessing game with great solutions for the guesses – which sounds like magic (in fact, “l₁-Magic” is the name of a popular Matlab routine that provides a solution).

Donoho and Candes are the prime-movers of Compressive Sensing (CS) and related theories and their pedigrees are impressive (Donoho is a MacArthur "genius award" winner). For engineers, the simplest context in which to understand CS is data acquisition. If a time series is a sum of 2 sinusoids, we have to sample it at twice the frequency of the sinusoid of the highest frequency (at Nyquist rate). Depending on the relative frequencies of the sinusoids, we may have to acquire hundreds of samples to be able to reconstruct the original time series faithfully. CS theory asserts that you only need about 8 random samples and not hundreds to faithfully reconstruct the data! On the face of it, this assertion looks absurd in that it flies in the face of the long-standing understanding of Nyquist criterion.

However, a glimmer of insight may arise when we take note of the fact that there are only 2 sinusoids in the data! Somehow, if we can gather the information about these 2 sinusoids from 8 random samples, we may be able to reconstruct the data fully. Under such “rank limited” situation (along with a few easy-to-meet restrictions), CS theory provides a way to completely recreate the original data.

CS theory is accessible and 3 easy to read intros are (1) Candes & Wakin, “Introduction to Compressive Sampling”, IEEE Signal Processing Magazine, 2008, (2) Baraniuk, “Compressive Sensing lecture notes”, IEEE Signal Processing Magazine, 2007 and (3) Candes & Plan, “Matrix Completion with Noise”, Proceedings of the IEEE, 2010.

As you will find from these and other excellent articles on the topic, the approach is to solve a constrained minimization problem using a certain norm. l₂-norm we are used to is largely unsuitable for this task because you do not almost always reach the desired solution (perhaps the reason why no one saw this solution till 2000’s). The so-called l₀-norm will work but is not tractable. However, l₁-norm (or the “taxi-cab” metric) does the trick. Many linear programming solutions exist; MATLAB implementations are available from multiple websites.

Data Analytics:

The references I mentioned above provide motivation from the data analytics domain (mostly from the Netflix recommendation challenge). Let me give an example from Retail analytics.

In Retail/CPG analytics, large amount of shopper data is collected via loyalty cards, transaction logs, credit card information, etc. All of these data are collected and collated into a large data matrix. For example, the data matrix may contain for each shopper (each row of a matrix), the amount they spent over a year on soaps from different brands (each column is a CPG brand). A relatively small data set in this business may have 5 or 10 million entries; however most of the entries will be missing (usually marked as “zero”). This stands to reason because I may buy only 1 or 2 brands of the 100’s of CPG soap brands; so the rest of my row will be zeros. In an example, we had 93% of the entries as zeros!

To relate this situation to the sum of sinusoids sampling, remember that the signal was “rank-limited” in that it was made up of only 2 sinusoids. Low-rank is one of the primary reasons that CS works. In the case of the soap data matrix, we again have a low-rank situation since the underlying preference for soap depends only on a few parameters such as smell, anti-bacterial property, color, cost, etc. In other words, if we do an eigen-decomposition of the true data matrix, only a few eigenvalues will be significant. Hence, using the linear programming approach and minimizing the l₁-norm, we are able to reconstruct the other 93% of the entries!

So now, we have a tractable (“magical”) solution to identify the entries of the “soap” data matrix. What do these entries tell us?

The reconstructed entry is the Data Scientist’s best prediction of what a shopper would spend on a certain CPG soap brand. This is hugely valuable – this is an excellent proxy for shopper’s propensity of purchase of a particular brand. A CPG can group the shoppers based on their purchase propensities, identify a group for whom it is low and target them with advertisements or discount offers to “switch” them. This information can be used by media buyers to optimize their ad dollar ‘spend’. Knowing which shoppers visit a specific store location, Retailers can assay their ‘spends’ and stock their shelves appropriately. The applications are virtually limitless.

small BIG Data:

If we can reconstruct 93% of the data from a 7% random sample as in the example above, who needs BIG data?

Clearly, we do not need BIG data *collection*. But we still need to regenerate BIG data (all the data matrix entries). But perhaps we do not need to store it; it can be regenerated at will (convergence of the algorithms seem fast). So, we do not need BIG data collection or storage but we do need to process BIG data. Seem to point to in-memory BIG data solutions for this type of data analytics applications . . . next few months will tell.

Network Dynamics & Coupling: Shannon’s Reverie Reprised . . . updated

Shannon’s (fictional) Reverie . . .

Claude Shannon woke up one morning and said to himself, “Think of how our brains operate – it habituates to repeated stimuli but pays attention to a rare stimulus; things that are rare must carry a lot of information!” So, what do I know about quantifying rare or unlikely things? I know that things that are highly likely are highly probable; so unlikely-things or novelty can be thought of as the inverse of probability. But snap! Probability goes from 0 to 1; I need a “squashing” function around it so that the novelty measure does not blow up fast but at the same time, very low probability things (highly novel things) are highly weighted. How about . . .?

A bit of cleanup via taking expectations, probability density functions and some proper logarithms and we have Shannon’s famous equation for “information”,

When you reduce a (joint) probability density function to a scalar, there is a lot that you throw away; the “trick” is that the scalar that you come up with captures some aspect of reality that is *useful*. As the explosion of communication technologies in the past few decades shows, Shannon’s scalar sure did!

I am not claiming that this is how Shannon did his research but this is one way to approach new insights that you may have and their quantification.

Social and Other Networks:

In my recent blog on Social Networks, “What does ‘Emergent Properties in Network Dynamics’ have to do with Shopping?”, I noted the following: “Facebook connects us in a vast network – this is only a first step. The deep reason for the fascination with social networking can be understood from the shopper example. Shoppers are enmeshed in an ever-changing network of social interactions and preferences. Today in Retail Analytics, data are treated as isolated bits of information. In reality, data exist in *embedded* forms in preference and influence networks of the shopper as well as distributed in time and space.”

As you know, interest in understanding such Social Networks and controlling their “dynamics” via “influence functions” of nodes, etc., are at a fever pitch – advertising, retail and many other day-to-day eCommerce activities can benefit from a better conceptualization and quantification of social network dynamics.

We know that “coupling” in networks generate very interesting dynamics (see, Steven Strogatz, “Sync: The emerging science of spontaneous order”, 2003, for a very readable overview).  Consider the ultimate of all networks – the brain. When we do “brain mapping”, interesting patterns arise. The brain mapping pictures show scans of a “depressed” and a “non-depressed” person. In the Depressed case, the brain regions are NOT coupled whereas in the non-depressed or Normal case, there is significantly more coupling and more uniform activity across the entire brain. Note however that if we looked at such a scan for an epileptic patient during a seizure, the scan will be all “lit up” showing nearly-complete coupling – that is a degenerate case!

Reprising the Reverie . . .

Coming back to healthy coupling and following Shannon’s (fictional) thinking process outlined in the first paragraph, what do I know about quantifying “coupling”? I know that when the underlying sources are coupled, their “stimulation” of the neocortex is uniform and they show up equally across the network at the same time, much like a single “wavefront” that reaches all the regions simultaneously. Imagine you are at a beach looking out to the sea and gentle waves are rolling in – let us say in parallel to the beach. If you are standing knee-deep in the water and look in a direction parallel to the beachfront (i.e., up or down the beach), the spatial frequency in your “look direction” (or the frequency of “corrugation”) is 0 cycles/meter! Much like the ocean waves, the single waverfront of stimulation is nearly “constant” across the distributed neocortex and its relevant strength can be thought of as the power at zero frequency.

I happen to know that power at zero frequency is called “Scale of Fluctuation” or “θ” in random field theory. From the previous work of Eric Vanmarcke (“Random Fields”, 1983, with an updated edition in 2010),

For the initiated, the equation and the accompanying figures below are hugely meaningful! In the figure, the “height”, (g(0) times π ) and the “area” under the normalized autocorrelation function, ρ(τ), are marked in blue – this is “θ”! This is the graphical meaning of Vanmarcke’s equation for θ.

The result shown above is for a time series. For the brain mapping case, “θ” is 4π²g(0,0) of its 2-D normalized spectral density (same pattern follows for higher dimensional random fields). Calculations of θ for 1-D and 2-D cases are straight forward; ways to calculate “instantaneous” values of θ are also available using Kalman Filtering (introduced in my past publication, “Instantaneous Scale of Fluctuation Using Kalman-TFD & Applications in Machine Tool Monitoring”). Some curious properties of θ for 2^nd order linear time invariant systems were also developed there. To recap the highlights –

From discrete-time linear time-invariant system principles, we know that constant damping ratio and undamped natural frequency contours in the z-plane are as shown on the left.

It is notable that for a second-order system, the constant θ contours shown on the right have remarkably simple geometric shapes. In fact, for θ = 1, the equation is quartic but very similar to a circle with origin at (0.5 + j0) and radius = 0.5!

Equation for θ = 1 contour is (x² + y²) ² + x² + y² – 2x = 0

There are more details in PG Madhavan, Theory and estimation techniques for Random Field Theory and "Theta" with practical applications: Instantaneous Scale ofFluctuation Using Kalman-TFD & Applications in Machine Tool Monitoring, SPIEProceedings, SPIE Vol. 3162, pp. 78-89, 1997.

Similar to Shannon’s scalar, H, θ reduces the joint probability density function to a scalar. Does θ capture some aspect of reality that is useful? The constant θ contours above seem to imply great significance as fundamental as natural frequency and damping – but at this time, such insights are not forthcoming!

Similar to Shannon’s scalar, H, θ reduces the joint probability density function to a scalar. Does θ capture some aspect of reality that is useful? Some real-world applications of θ from the past (see its use for machine tool chatter prediction) point to the following physical insights.

While highly speculative, previous studies and our “Shannon approach” suggest that θ is proportional to “coupling” and to “order” in a distributed node system whereas it is inversely related to “degrees of freedom (df)”. In the case of “df”, the concept is that more degree of freedom is a “dangerous precipice” for a distributed system where different parts are de-synchronized and they can spin off in different directions - pandemonium can ensue!

Large θ seems to indicate an ordered, widely-cooperative and well-functioning network; however, it is conceivable that a large θ may also indicate degenerate cases such as epileptic seizure or full-fledged chatter conditions (extreme cases of coupled sources and distributed action). An example is shown below.

Large θ on the left is a hallmark of “distributed order” whereas the large θ on the right, that of “locked-in order”. Low θ condition in the middle is visually indicative of disorder and the potential for degeneracy!

θ in Social Networks:

To help develop our intuition, let us consider some snapshots of geographcally distributed network maps. We have (1) Internet activity over continental United States, (2) LinkedIn infographic map and (3) Facebook social network map.

We notice strong coupling in the Eastern half of US among Internet nodes and similar features in the LinkedIn and Facebook networks. Our intuition is that the *bright spots* obvious in the Northeast US of the Internet map or the EU area in the Facebook map indicate more “correlated” activity. For simple network maps, we have developed primitive methods to estimate θ based on correlation functions.

Before we leave this blog, consider the brain map and the US map of the Internet. What we see in these pictures can be called “surface structure”, i.e., observed or measureable quantities. In the brain, the Surface Structure is created by activity deep within the brain (I am NOT referring to Chomskian linguistics model here). In the past, naïve physical modeling has conceptualized dipole oscillators in the “deep structure” of the brain giving rise to the Surface Structure as a starting point for theorizing. In the case of the brain, there are indeed Deep Structures (nuclei and ganglia and their dendritic potentials) giving rise to voltage variations on the scalp surface (earthquake tremors recorded on the surface of the earth and activity deep in the earth’s crust form a similar model).

Clearly, the Surface Structure of the Internet cannot be related to any actual Deep Structure in a physical model – there is no mechanical turk behind the Internet pulling the strings! However, even in such cases, conceptualizing observed activity as the resultant of implicit Deep Structure may be useful in developing analysis methods. The hope is that the physical model of network activity utilizing the concept of explicit or implicit deep structures with internal coupling will help advance our “analytics” tools for the extraction of patterns and information from spatially and temporally distributed networked systems.

www.JINinnovation.com

Dr. PG Madhavan was CTO Software Solutions at Symphony Teleca Corp. Previously, he was the CTO & VP Engineering for Solavei LLC and the Associate Vice President--Technical Advisory for Global Logic Inc.  PG has 20+ years of software products, platforms and framework experience in leadership roles at major corporations such as Microsoft, Lucent, AT&T and Rockwell and startups, Zaplah Corp (Founder and CEO) and Solavei. Application areas include mobile, Cloud, eCommerce, banking, retail, enterprise, consumer devices, M2M, digital ad media, medical devices and social networking in both B2B and B2C market segments.  He is an innovation leader driving invention disclosures and patents (12 issued US patents) with a Ph.D. in Electrical & Computer Engineering.  More about PG at www.linkedin.com/in/pgmad