A discrete-time distributed algorithm for minimum l₁-norm solution of an under-determined linear equation set

This paper proposes a discrete-time, distributed algorithm for multi-agent networks to achieve the minimum l₁-norm solution to a group of linear equations known to possess a family of solutions. We assume each agent in the network knows only one equation and can communicate with only its neighbors. The algorithm is developed based on a combination of the projection-consensus idea and the sub-gradient descent method. Given the underlying network graph to be directed and strongly connected, we prove that the algorithm enables all agents to achieve a common minimum l₁-norm solution. The major difficulty to be dealt with is the non-smooth nature of the norm and the lack of strict convexity of the associated relevant performance index.