Communications of the ACM
To Handle Big Data, Shrink It
A new algorithm developed by researchers at the Massachusetts Institute of Technology finds the smallest approximation of a matrix that guarantees reliable computations.
Credit: Jose-Luis Olivares/MIT
Massachusetts Institute of Technology (MIT) researchers Richard Peng and Michael Cohen have developed an algorithm that finds the smallest possible approximation of a matrix that guarantees reliable computations. In addition, for all classes of problems, the algorithm finds the approximation as quickly as possible.
The researchers say the algorithm is a major improvement over previous techniques, especially for engineering and machine-learning problems. They note the algorithm is optimal for condensing matrices under any "norm." A norm is a measure of the distance between a given row of a condensed matrix and a row of the original matrix. The Manhattan distance, or 1-norm, is the first root of the sum of differences raised to the first power, and the Euclidean distance, or 2-norm, is the square root of the sum of differences raised to the second power.
The new algorithm condenses matrices under the 1-norm as well as it does under the 2-norm. In addition, the researchers mathematically proved the 2-norm algorithm will yield reliable results under the 1-norm.
"It's highly elegant mathematics, and it gives a significant advance over previous results," says University of California, Berkeley professor Richard Karp.
Peng and Cohen will present their algorithm next month at the 47th ACM Symposium on Theory of Computing (STOC 15) in Portland, OR.
From MIT News
View Full Article
Abstracts Copyright © 2015 Information Inc., Bethesda, Maryland, USA
No entries found