# Unraveling the Matrix

##### Jul 29, 2010 by Larry Hardesty

A new way of analyzing grids of numbers known as matrices could improve signal-processing applications and data-compression schemes.

Among the most common tools in electrical engineering and computer science are rectangular grids of numbers known as matrices. The numbers in a matrix can represent data: The rows, for instance, could represent temperature, air pressure and humidity, and the columns could represent different locations where those three measurements were taken. But matrices can also represent . If the expressions t + 2p + 3h and 4t + 5p + 6h described two different mathematical operations involving temperature, pressure and humidity measurements, they could be represented as a matrix with two rows, [1 2 3] and [4 5 6]. Multiplying the two matrices together means performing both mathematical operations on every column of the data matrix and entering the results in a new matrix. In many time-sensitive engineering applications, multiplying matrices can give quick but good approximations of much more complicated calculations.

In a paper published in the July 13 issue of Proceedings of the National Academy of Science, MIT math professor Gilbert Strang describes a new way to split certain types of matrices into simpler matrices. The result could have implications for software that processes video or audio data, for compression software that squeezes down digital files so that they take up less space, or even for systems that control mechanical devices.

Strang’s analysis applies to so-called banded matrices. Most of the numbers in a banded matrix are zeroes; the only exceptions fall along diagonal bands, at or near the central diagonal of the matrix. This may sound like an esoteric property, but it often has practical implications. Some applications that process video or audio signals, for instance, use banded matrices in which each band represents a different time slice of the signal. By analyzing local properties of the signal, the application could, for instance, sharpen frames of video, or look for redundant information that can be removed to save memory or bandwidth.

Working backwards

Since most of the entries in a banded matrix — maybe 99 percent, Strang says — are zero, multiplying it by another matrix is a very efficient procedure: You can ignore all the zero entries. After a signal has been processed, however, it has to be converted back into its original form. That requires multiplying it by the “inverse” of the processing matrix: If multiplying matrix A by matrix B yields matrix C, multiplying C by the inverse of B yields A.

But the fact that a matrix is banded doesn’t mean that its inverse is. In fact, Strang says, the inverse of a banded matrix is almost always “full,” meaning that almost all of its entries are nonzero. In a signal-processing application, all the speed advantages offered by banded matrices would be lost if restoring the signal required multiplying it by a full matrix. So engineers are interested in banded matrices with banded inverses, but which matrices those are is by no means obvious.

In his PNAS paper, Strang describes a new technique for breaking a banded matrix up into simpler matrices — matrices with fewer bands. It’s easy to tell whether these simpler matrices have banded inverses, and if they do, their combination will, too. Strang’s technique thus allows engineers to determine whether some promising new signal-processing techniques will, in fact, be practical.

Faster than Fourier?

One of the most common digital-signal-processing techniques is the discrete Fourier transform (DFT), which breaks a signal into its component frequencies and can be represented as a matrix. Although the for the Fourier transform is full, Strang says, “the great fact about the Fourier transform is that it happens to be possible, even though it’s full, to multiply fast and to invert it fast. That’s part of what makes Fourier wonderful.” Nonetheless, for some signal-processing applications, banded matrices could prove more efficient than the Fourier transform. If only parts of the signal are interesting, the bands provide a way to home in on them and ignore the rest. “Fourier transform looks at the whole signal at once,” Strang says. “And that’s not always great, because often the signal is boring for 99 percent of the time.”

Richard Brualdi, the emeritus UWF Beckwith Bascom Professor of Mathematics at the University of Wisconsin-Madison, points out that a mathematical conjecture that Strang presents in the paper has already been proven by three other groups of researchers. “It’s a very interesting theorem,” says Brualdi. “It’s already generated a couple of papers, and it’ll probably generate some more.” Brualdi points out that large data sets, such as those generated by gene sequencing, medical imaging, or weather monitoring, often yield matrices with regular structures. Bandedness is one type of structure, but there are others, and Brualdi expects other mathematicians to apply techniques like Strang’s to other types of structured matrices. “Whether or not those things will work, I really don’t know,” Brualdi says. “But Gil’s already said that he’s going to look at a different structure in a future paper.”

Explore further: Hyperbolic homogeneous polynomials, oh my!

## Related Stories

#### Discovery could lead to more difficult Sudoku puzzles

Feb 13, 2010

(PhysOrg.com) -- A new analysis of number randomness in Sudoku matrices could lead to the development of more difficult and multi-dimensional Sudoku puzzles. In a recent study, mathematicians have found that ...

#### Explained: The Discrete Fourier Transform

Nov 25, 2009

(PhysOrg.com) -- In 1811, Joseph Fourier, the 43-year-old prefect of the French district of Isčre, entered a competition in heat research sponsored by the French Academy of Sciences. The paper he submitted ...

#### An easy way to find a needle in a haystack by removing the haystack

Jun 18, 2009

Researchers at the Max Planck Institute for Chemical Ecology in Jena and their colleagues from the Czech Academy of Sciences in Prague have developed a new method to quickly and reliably detect metabolites, ...

#### Renesas Develops Massively Parallel Processor Based on Matrix Architecture

Feb 09, 2006

Renesas Technology Corp. today announced the development of a massively parallel processor based on a matrix architecture suitable for image and audio multimedia data processing.

#### Capillary formation’s mechanical determinants: One growth factor can have many effects

Mar 09, 2009

(PhysOrg.com) -- Harvard researchers have established a link between the growth of blood vessels and the mechanical stresses caused by the environment within which the vessels grow, a new understanding that ...

#### Hydrogels provide scaffolding for growth of bone cells

Aug 17, 2008

Hyaluronic hydrogels developed by Carnegie Mellon University researchers may provide a suitable scaffolding to enable bone regeneration. The hydrogels, created by Newell Washburn, Krzysztof Matyjaszewski and Jeffrey Hollinger, ...

## Recommended for you

#### Best of Last Week—Confirmed Earth-sized planet, testing twin paradox w/o a spaceship and news we all peak at 24

33 minutes ago

(Phys.org) —Reader response to last week's roundup of the most important stories we covered during the prior week was overwhelmingly positive. Thus, we will be continue posting them, at least for now. So ...

#### Hyperbolic homogeneous polynomials, oh my!

52 minutes ago

Cutting-edge mathematics today, at least to the uninitiated, often sounds as if it bears no relation to the arithmetic we all learned in grade school. What do topology and combinatorics and n-dimensional ...

#### Aboriginal people – how to misunderstand their science

1 hour ago

Just one generation ago Australian schoolkids were taught that Aboriginal people couldn't count beyond five, wandered the desert scavenging for food, had no civilisation, couldn't navigate and peacefully ...

#### Zero hour contracts are 'tip of the iceberg' of damaging shift work, say researchers

2 hours ago

New report shows that zero hour contracts are only one of a wide number of flexible employment practices that are abused by managers - leading to financial insecurity, anxiety and stress in the workforce. ...

#### Poll: Big Bang a big question for most Americans

6 hours ago

Few Americans question that smoking causes cancer. But they have more skepticism than confidence in global warming, the age of the Earth and evolution and have the most trouble believing a Big Bang created the universe 13.8 ...

#### Egypt archaeologists find ancient writer's tomb

Apr 19, 2014

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...

## More news stories

#### Best of Last Week—Confirmed Earth-sized planet, testing twin paradox w/o a spaceship and news we all peak at 24

(Phys.org) —Reader response to last week's roundup of the most important stories we covered during the prior week was overwhelmingly positive. Thus, we will be continue posting them, at least for now. So ...

#### Teachers' scare tactics may lead to lower exam scores

As the school year winds down and final exams loom, teachers may want to avoid reminding students of the bad consequences of failing a test because doing so could lead to lower scores, according to new research published ...

#### Hyperbolic homogeneous polynomials, oh my!

Cutting-edge mathematics today, at least to the uninitiated, often sounds as if it bears no relation to the arithmetic we all learned in grade school. What do topology and combinatorics and n-dimensional ...

#### Poll: Big Bang a big question for most Americans

Few Americans question that smoking causes cancer. But they have more skepticism than confidence in global warming, the age of the Earth and evolution and have the most trouble believing a Big Bang created the universe 13.8 ...

#### Zero hour contracts are 'tip of the iceberg' of damaging shift work, say researchers

New report shows that zero hour contracts are only one of a wide number of flexible employment practices that are abused by managers - leading to financial insecurity, anxiety and stress in the workforce. ...

#### New material coating technology mimics nature's lotus effect (w/ video)

Ever stop to consider why lotus plant leaves always look clean? The hydrophobic – water repelling – characteristic of the leaf, termed the "Lotus effect," helps the plant survive in muddy swamps, repelling ...

#### A new key to unlocking the mysteries of physics? Quantum turbulence

The recent discovery of the Higgs boson has confirmed theories about the origin of mass and, with it, offered the potential to explain other scientific mysteries.

#### Hydrogen sulfide nanoreporters gather intel on oil before pumping

(Phys.org) —Scientists at Rice University have created a nanoscale detector that checks for and reports on the presence of hydrogen sulfide in crude oil and natural gas while they're still in the ground.

#### Study of equatorial ridge on Iapetus suggests exogenic origin

(Phys.org) —A combined team of researchers from Brown University in Rhode Island and the Lunar and Planetary Institute in Texas is suggesting in a paper they've uploaded to the preprint server arXiv, that a ...

#### Researchers discover novel function of protein linked to Alzheimer's disease

A research team led by the National Neuroscience Institute (NNI) has uncovered a novel function of the Amyloid Precursor Protein (APP), one of the main pathogenic culprits of Alzheimer's disease. This discovery ...