Computer Vision News - September 2016

CVN: Is it because coresets are so powerful that you chose them as your main technique? Feldman: Yes - There are many social, academic and industrial reasons why we use coresets these days. If you know how to optimize a program and use the original data with the small data, of course you get some errors. Surprisingly, the results on the coresets are usually better than the original data . If you give me data to find the optimal solution, I can do better by moving some of the data. If we just have strange heuristics that give you some number without any proof of why it’s good or bad, usually these heuristics only find local minima. The coresets remove a lot of noise, thus the local minima are much smaller and better. In some sense, data reduction removes most of the noise. That’s how we get better results compared to running the algorithm on the original coreset. It’s very good for business: we still use all of your expert knowledge. But also academically, I started using the coresets for theoretical problems. These days, I’m using the coresets for drones, image processing, computer vision robotics and EEG. CVN: Which kind of algorithm works better and on which kind of problems? Feldman: For many problems we can prove that a small coreset does not exist: removing one input point would yield a very bad approximation. In this discussion we assume that a small coreset exists, but we need to find it and prove its guarantees for every new problem. As I said, we try to find general solutions for problems that don’t satisfy specific requirements. This is a kind of optimization. We don’t expect anyone to find one single technique to optimize all the problems in the world. CVN: In what way is the coreset that you use different from the coreset for k-means used by Sariel Har-Peled? Feldman: It’s not! Over the years, we have developed coresets for different problems and we keep improving and redefining them so that we can solve the problems. With every problem, we have a long line of research. In computer vision, there are numerous problems that I believe we can solve using coresets. Researchers from theoretical computer science are not interested in or (in the more common case) not familiar with this kind of problems. Coresets are a new paradigm. It is more a state of mind than an exact mathematical definition because the exact definition changes from paper to paper. Actually, the number of definitions is very similar to the number of papers on coresets. “ I hope to bridge the gap between theory and practice using these coresets ” Computer Vision News Guest 21 Guest