Donald Goldfarb | Finding a Way Around Too Much Data

Donald Goldfarb
Alexander and Hermine Avanessians Professor of Industrial Engineering and Operations Research
This profile is included in the publication Excellentia, which features current research of Columbia Engineering faculty members.
                                    Photo by Eileen Barroso

Computing power has grown rapidly, but not as fast as the problems researchers aspire to solve.

“We’re dealing with enormous problems, problems so large we can’t even store all the numbers in computer memory at the same time. We cannot rely on the same methods we used for smaller problems and expect to solve them,” said Donald Goldfarb.

His work on extracting movement from surveillance videos provides an example. On surveillance videos, the background never changes. One frame looks very much like the next, except for the people moving through the space. Each frame has roughly 20,000 pixels.

“To extract moving images from a couple of minutes of video, we need to process 50 million variables and 25 million linear equations,” Goldfarb said.

Doing it by brute force—one computation after the other—would take days on powerful computers. Instead, he developed a systematic optimization procedure, or algorithm, that lets a simple workstation remove the background in under an hour. Goldfarb has a long history of developing powerful optimization algorithms.

Some of his early algorithms are used in commercial software to optimize complex systems. They make it possible, for example, to adjust refinery operations on the fly instead of spending weeks plotting a production schedule.

Goldfarb’s work goes beyond just finding fast ways to solve difficult problems.

“I try to prove that the algorithms I develop are not just fast for a specific problem, but will work well for any similar problem,” he said. “It’s like providing a certificate guaranteeing the algorithm’s performance.”

He also tries to discover properties about different classes of algorithms. Recently, he has focused on convex functions. Like many algorithms, they recast algebraic problems in geometric terms in order to estimate answers more rapidly. Goldfarb likens a convex function to a bowl with the minimum, or optimal, value at the bottom. Constraints usually push the answers to any given problem somewhere along the sides of the bowls.

“If you’re sitting on the side, you can see every other point inside the bowl. If you look around and every other point is higher, then you are at the optimal point,” Goldfarb explained.

Recently, Goldfarb used convex functions to optimize a method to produce MRI and CT scan images using only one-fifth the radiation. “The algorithm enables us to get an appropriate image with fewer measurements, so patients only have to spend one-fifth as much time in these machines,” Goldfarb said.

B.Ch.E., Cornell, 1963; M.A., Princeton, 1965; Ph.D., Princeton, 1966

500 W. 120th St., Mudd 510, New York, NY 10027    212-854-2993