Computer Vision News - September 2016

It is the first time that we discuss the coresets , a powerful technique which enables the use of smaller sets of data instead of larger ones without compromising the quality of the output. To learn more about it, we decided to interview one of the most important researchers in the field: Dr. Dan Feldman , who after three years at the Computer Science and Artificial Intelligence Lab of the MIT (CSAIL ), is now Director of the Robotics and Big Data Lab and Senior Lecturer at the Computer Science Department of the University of Haifa . He was kind enough to tell us more. Computer Vision News: What are coresets and why are they so important? Why are they so powerful? Why should we use them? Dan Feldman: The main idea is that in computer science we usually have a problem that someone suggests, let’s say clustering. Different solutions will be suggested to solve this problem. We usually want to develop a better algorithm over time with an improved running time, memory or space. With coresets, the philosophy is different. Instead of trying to suggest another algorithm, we want to prove that we can reduce the data, so that running existing algorithms on the reduced "small data" will provably give approximated result, as running them on the original "Big data". We can usually reduce the data, not by half, but by order of magnitude: for example, from n to log(n). This is done, not by designing a new algorithm for solving the problem, but by just running the new algorithm and existing algorithm on small compressions. Unlike other compression techniques like zip or mp4, coreset is data reduction and not just compression of the input in the sense that it’s problem-dependent. A point may be important for one problem, but not important for another problem. We keep seeing papers on optimization for new problems, but we still have general techniques such as linear and quadratic programming. We have Singular Value Decomposition (SVD) and Principal Component Analysis (PCA). We have the derivatives. We have general techniques on how to optimize functions if they have specific properties. These days we also try to find more general techniques for coreset constructions. 20 Computer Vision News Guest Dan Feldman, University of Haifa Guest “ Unlike other compression techniques like zip or mp4, coreset is data reduction and not just compression of the input ”