Close this search box.

João Mota Receives 2015 IEEE SPS Young Author Best Paper Award

Alumnus in ECE from IST and CMU: João Mota
João Mota Receives 2015 IEEE SPS Young Author Best Paper Award

JMota 2015 João Mota was recently distinguished with the 2015 IEEE SPS Young Author Best Paper Award for the paper “Distributed Basis Pursuit”, published at the IEEE Transactions on Signal Processing, Volume: 60, No. 4, on April 2012. The paper was written by João Mota, with his advisors João Xavier (IST), Pedro M.Q. Aguiar (IST), and Markus Püschel (CMU). “This award couldn’t have been more timely, as I am currently applying for academic positions. And having such an award will be a major asset,” says João Mota.

João Mota got his dual degree Ph.D. in Electrical and Computer Engineering (ECE), at Instituto Superior Técnico (IST) and Carnegie Mellon University (CMU), in 2013, with the dissertation titled “Communication-Efficient Algorithms For Distributed Optimization.” Afterwards he become a Postdoctoral Researcher at the University College London. João Mota’s research interests include optimization theory and algorithms, big data processing, compressed sensing, distributed algorithms, control, machine learning, and sensor networks.

CMU Portugal Program: What is the paper about?
João Mota (JM): The paper describes a very efficient distributed algorithm to solve a problem called Basis Pursuit. Intuitively, and using images as an example, Basis Pursuit enables reconstructing images from very few measurements; a measurement can be an individual pixel or something more complex, for example, the result of multiplying all the pixels of the image by a random number and adding up the resulting (random) numbers. Using just a few measurements of this type, Basis Pursuit can still reconstruct the image by exploiting the image’s redundant information. In fact, most signals we deal with, from audio and video to sensor and financial data, contain redundant information and, thus, can be compressed. This is one of the reasons why Basis Pursuit and the theory that explains how it works, Compressed Sensing, have become so popular. They have been used to improve several technologies, for example, Magnetic Resonance Imaging (MRI), and even to create new ones such as the single-pixel camera. Our paper considers a distributed scenario in which the measurements are spread over the nodes of a network, for example, a sensor network or a computer cluster. No node has access to the full data neither can it control the other nodes. It is thus a completely decentralized scenario. Such a scenario arises in situations where we want reliability (if one node stops working it does not jeopardize the entire system) or simply when the amount of data is so large that it cannot be stored or processed by a single computer.

CMU Portugal Program: What are the main findings of this paper?
JM: The paper proposes an algorithm that specifies what each node has to do, in particular the messages each node exchanges with its neighbors in order to solve the Basis Pursuit problem. At the end of the algorithm, all nodes know the solution of the problem as if it were solved in a centralized way, with all the data known at a single location. Although there are several distributed algorithms that also solve Basis Pursuit, what makes our algorithm special is its efficiency: namely, it solves the problem using much fewer communications than what competing algorithms use. Since the paper was published, however, other researchers have proposed algorithms that solve Basis Pursuit even more efficiently.

CMU Portugal: What was the impact of the paper in this research field?
JM: The award notice didn’t give the reason for the award, but I speculate that it was because of the work it made possible afterwards. In particular, in our subsequent work, we generalized the algorithm to solve other distributed problems, for example, to perform data inference, compute network routes, and design control systems. To my knowledge, there is no more efficient way to solve these problems than with our generalized algorithm. The awarded paper thus lays the foundations for creating this extremely efficient distributed algorithm.

November 2015

Article Related:
João Mota Uses Distributed Algorithms to Solve Optimization Problems
João Mota and his Qualifier Exam Experience

Call for Applications for Doctoral Program Scholarships 2016/2017 is now open!