Wednesday, December 15, 2010

CS: Bob's Confusion Coherence, CS Python, Privacy and Compressive Sensing: Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies, Real-time Visual Tracking Using Sparse Representation

Something is awesome in the state of  Denmark, Bob is continuing his smarter conversation with Phil Alejandro and Guan  in
So you have some vectors that are yielding success and others yielding failure, maybe an empirical analysis using some simple tools of machine learning could give some perspective on the type of vectors in the dictionary that are failing OMP, I am sure the Nuit Blanche readers have better ideas.

Miketrumpis has just released a Python implementation of a compressive sensing demo from Justin Romberg's Signal Processing.. From the Readme file:

Demo of Compressive Sampling in Image Reconstruction

This code is essentially a Scientific Python port of Justin Romberg's Compressive Sampling (CS) demo, which accompanied his publication

J. Romberg, "Imaging via Compressive Sampling," Signal Processing Magazine, March 2008.

The original MATLAB code can be downloaded from this web site

If you are into compressive sensing and looking for a job, like I am, you might want to lobby potential employers that being a Chief Privacy Officer entails some unique insight about Compressive Sensing. It happened with Netflix, it will happen to HPN, and it's not a question of disappearing laptops with thousands of social security numbers anymore as the ability to clone your database with few queries.. The current war between Facebook and Google about the assymetry between their social graphs is a definite indication that these techniques are likely to be refined. But beyond electronic data, inverse estimation of pollution sources, diseases such as cancer from sensors in waste streams or electricity grid prediction from few smart sensors are definitely potential target of investigation. using the same tools. Without further due here is: Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies by Arthur Asuncion, Michael Goodrich. The abstract reads:
In this paper, we study sparsity-exploiting Mastermind algorithms for attacking the privacy of an entire database of character strings or vectors, such as DNA strings, movie ratings, or social network friendship data. Based on reductions to nonadaptive group testing, our methods are able to take advantage of minimal amounts of privacy leakage, such as contained in a single bit that indicates if two people in a medical database have any common genetic mutations, or if two people have any common friends in an online social network. We analyze our Mastermind attack algorithms using theoretical characterizations that provide sublinear bounds on the number of queries needed to clone the database, as well as experimental tests on genomic information, collaborative filtering data, and online social networks. By taking advantage of the generally sparse nature of these real-world databases and modulating a parameter that controls query sparsity, we demonstrate that relatively few nonadaptive queries are needed to recover a large majority of each database.
The $\ell_1$ tracker obtains robustness by seeking a sparse representation of the tracking object via $\ell_1$ norm minimization \cite{Xue_ICCV_09_Track}. However, the high computational complexity involved in the $ \ell_1 $ tracker restricts its further applications in real time processing scenario. Hence we propose a Real Time Compressed Sensing Tracking (RTCST) by exploiting the signal recovery power of Compressed Sensing (CS). Dimensionality reduction and a customized Orthogonal Matching Pursuit (OMP) algorithm are adopted to accelerate the CS tracking. As a result, our algorithm achieves a real-time speed that is up to $6,000$ times faster than that of the $\ell_1$ tracker. Meanwhile, RTCST still produces competitive (sometimes even superior) tracking accuracy comparing to the existing $\ell_1$ tracker. Furthermore, for a stationary camera, a further refined tracker is designed by integrating a CS-based background model (CSBM). This CSBM-equipped tracker coined as RTCST-B, outperforms most state-of-the-arts with respect to both accuracy and robustness. Finally, our experimental results on various video sequences, which are verified by a new metric---Tracking Success Probability (TSP), show the excellence of the proposed algorithms.

No comments: