Taming Heterogeneity and Complexity of Embedded Control

Optimization Methods for the Sphere Packing Problem on Grassmannians

 

Christian Lageman—Uwe Helmke

Department of Mathematics,University WürzburgAm Hubland97074 WürzburgGermany{lageman, helmke}@mathematik.uni-wuerzburg.de

ABSTRACT. We present two algorithms to compute optimal sphere packings on the Grassmann manifold. One is based on a nonsmooth cost function and a generalized gradient descent on the m-fold Grassmannian. For the generalized gradient descent we introduce a generalization of Clarke’s generalized gradient in a Riemannian geometry setting. The other algorithm uses a smooth approximation of the nonsmooth cost function and a Riemannian gradient descent. A comparison shows that the smooth algorithm has improved convergence properties.

KEYWORDS: Nonsmooth analysis, Gradient descent, Packing problems, Grassmann manifold, Cooperative control

1. Introduction

Motivated by recent work on capacity bounds in multi–antenna channel communications [ZHE 02] as well as by recent attempts to study motion and coordination problems in distributed control [COR 05] we consider packing problems on Riemannian manifolds. Other motivation is drawn from coding theory applications, as discussed in [CON 96]. More specifically, we are interested in computing packings by identical spherical balls in real Grassmann manifolds, which maximize the covered space. Thus, by identifying the Grassmannian Grass(n, k) with the Riemannian manifold of all rank k self-adjoint projection operators P, we consider ...