Navigation Content
University of Wisconsin Madison College of Engineering
You are here:
  1. Home > 
  2. News > 
  3. News archive > 
  4. 2014 > 
  5. Harnessing sparsity

Harnessing sparsity

Rob Nowak.

In a 2009 paper titled “Sparse reconstruction by separable approximation,” Rob Nowak and his colleagues presented a simple tool—yet one that represented years of work.

The tool, called SparSA, reduces a complex signal or system to a small number of relatively simple components. 

Since its publication in IEEE Transactions on Signal Processing, the paper’s influence has spread through a variety of fields that involve breaking down massive amounts of signals or statistics. The algorithm, for example, helps medical researchers reconstruct MRI images, enables surveyors to sift through topographical data gathered through plane-mounted Lidar systems, and gives genetic researchers greater precision in their search for the genes that cause particular diseases.  “These complex systems have a huge number of variables, but in any given situation only a small subset of them may be significantly affecting the behavior of the system,” Nowak says.

Nowak, the McFarland-Bascom professor of electrical and computer engineering, and the paper's co-authors, Computer Sciences Professor Stephen Wright and Professor Mário A.T. Figueiredo of the Instituto Superior Técnico in Portugal, recently received the 2014 IEEE W.R.G. Baker Award for the paper, which annually honors one outstanding paper published in an IEEE archival publication. It is one of the most prestigious awards IEEE presents.

The computing challenge SparSA tackles is essentially breaking apart data sets that describe very large systems of equations, all coupled together. The algorithm simplifies the problem by solving specially designed sequence of decoupled equations, enabling researchers to efficiently search over a huge set of possible solutions. 

Consider genetic researchers looking for key genes behind a disease. “The genes involved could be identified by measuring the expression levels of all genes in healthy and diseased cells,” Nowak says. “SparSA searches for the genes with expression levels that best correlate with and predict whether a cell is healthy or diseased, indicating which genes are most influential.”

That’s when all that “coupling” comes into play: “There are thousands of genes and the disease process may involve them in a complicated way. Directly searching all possible combinations of genes and effects is nearly impossible,” Nowak says. “SparSA sidesteps the challenge of a big data set by solving a simpler problem that takes much less time to solve than the brute-force search.”

By creating a solution that can be carried out quickly on a computer, Nowak and his co-authors have given researchers across disciplines a great deal of clarity in understanding complex problems. 

Scott Gordon