Related Experiment Videos
Linear coordinate-descent message passing for quadratic optimization
Guoqiang Zhang1, Richard Heusdens
1Department of Intelligent Systems, Delft University of Technology, Delft, the Netherlands. g.zhang-1@tudelft.nl
Abstract:
In this letter, we propose a new message-passing algorithm for quadratic optimization. The design of the new algorithm is based on linear coordinate descent between neighboring nodes. The updating messages are in a form of linear functions as compared to the min-sum algorithm of which the messages are in a form of quadratic functions. As a result, the linear coordinate-descent (LiCD) algorithm transmits only one parameter per message as opposed to the min-sum algorithm, which transmits two parameters per message. We show that when the quadratic matrix is walk-summable, the LiCD algorithm converges. By taking the LiCD algorithm as a subroutine, we also fix the convergence issue for a general quadratic matrix. The LiCD algorithm works in either a synchronous or asynchronous message-passing manner. Experimental results show that for a general graph with multiple cycles, the LiCD algorithm has comparable convergence speed to the min-sum algorithm, thereby reducing the number of parameters to be transmitted and the computational complexity.
Related Concept Videos
Quadratic Models
Quadratic Equations
Quadratic Equations in the Complex Number System
Linearization and Approximation
Equations of Motion: Rectangular Coordinates and Cylindrical Coordinates
When a particle moves relative to an inertial frame, the equations of motion can be expressed using rectangular components. If the motion is confined to the x-y plane, the equations having the x and y coordinates only can be used to simplify the mathematical representation.
However, when particles...
Coordination Number and Geometry