# A semidefinite programming hierarchy for covering problems in discrete
geometry

Cordian Riener  ,  Jan Rolfes  and  Frank Vallentin  Cordian Riener,
Department of Mathematics and Statistics, UiT The Arctic University of Norway,
9037 Tromsø, Norway<EMAIL_ADDRESS>Jan Rolfes, Friedrich-Alexander-
Universität Erlangen-Nürnberg, Cauerstr. 11, 91058 Erlangen, Germany
<EMAIL_ADDRESS>Frank Vallentin, Universität zu Köln, Department
Mathematik/Informatik, Abteilung Mathematik, Weyertal 86-90, 50931 Köln,
Germany<EMAIL_ADDRESS>
(Date: December 18, 2023)

###### Abstract.

In this paper we present a new semidefinite programming hierarchy for covering
problems in compact metric spaces.

Over the last years, these kind of hierarchies were developed primarily for
geometric packing and for energy minimization problems; they frequently
provide the best known bounds.

Starting from a semidefinite programming hierarchy for the dominating set
problem in graph theory, we derive the new hierarchy for covering and show
some of its basic properties: The hierarchy converges in finitely many steps,
but the first level collapses to the volume bound when the compact metric
space is homogeneous.

##  1\. Introduction

Let $(X,d)$ be a compact metric space. Frequently one asks for specific
configurations of finitely many points in $X$. Various performance measures
for such finite point distributions are investigated. Homogeneous measures,
like maximizing minimal distance between pairs of distinct points (packing),
or minimizing energy with respect to a potential function (energy
minimization), are most commonly used. These homogeneous measures have
inhomogeneous counterparts: Finding a point configuration which minimizes the
maximal distance of an arbitrary point in $X$ to the finite point distribution
(covering), or maximizing the minimal potential energy of an arbitrary point
in $X$ in the force field given by the charges of the point configuration
(max-min polarization). For a more detailed overview, we refer to the book of
Borodachov, Hardin, Saff [4].

Over the last years, semidefinite programming hierarchies, in the spirit of
the moment-SOS hierarchy in polynomial optimization, due to Lasserre, were
developed primarily for providing bounds for geometric packing and for energy
minimization problems; see de Laat, Vallentin [9], and de Laat [11]. Computing
these semidefinite programming bounds frequently yield the best known bounds.

In this paper we want to demonstrate that this approach is also applicable to
geometric covering problems.

We start by defining the covering problem formally. Let $X$ be a compact
metric space with distance function $d$. We denote closed metric balls of
radius $r$ and center $x$ by $\overline{B}(x,r)=\\{y\in X:d(x,y)\leq r\\}$. A
set of balls of radius $r$ is uniquely determined by the collection of its
centers $Y$. A set $Y$ of centers with the property $\bigcup_{y\in
Y}\overline{B}(y,r)=X$ is called a _covering_ of $X$. Since $X$ is compact,
there always exists a finite covering. The _covering number_
$\mathcal{N}(X,r)$ of the space $X$ and a positive number $r$ is the smallest
number of such balls with radius $r$ one needs to cover $X$. So,

$\mathcal{N}(X,r)=\min\left\\{|Y|:Y\subseteq X,\bigcup_{y\in
Y}\overline{B}(y,r)=X\right\\}.$

Determining the covering number is a fundamental problem in metric geometry
(see for example the classical book by Rogers [22]). Among others,
applications arise in the field of compressive sensing [13], approximation
theory and machine learning [7], in probability theory [16] and theoretical
quantum computing [20].

So far, upper bounds for the covering number of several specific metric spaces
are known. For a survey on this, we refer to Naszódi [19]. Using a greedy
approach, in the spirit Chvátal’s greedy approximation algorithm for the set-
covering problem, Rolfes and Vallentin [23] provide upper bounds for a wider
class of compact metric spaces. They showed that for every $\varepsilon$ with
$r/2>\varepsilon>0$ the inequalities

(1)
$\frac{1}{\omega_{r}}\leq\mathcal{N}(X,r)\leq\frac{1}{\omega_{r-\varepsilon}}\left(\ln\left(\frac{\omega_{r-\varepsilon}}{\omega_{\varepsilon}}\right)+1\right),$

holds, where $X$ is equipped with a probability measure $\omega$ satisfying
the following two conditions:

  1. (a)

$\omega(\overline{B}(x,s))=\omega(\overline{B}(y,s))$ for all $x,y\in X$, and
for all $s\geq 0$,

  2. (b)

$\omega(\overline{B}(x,\varepsilon))>0$ for all $x\in X$, and for all
$\varepsilon>0$.

By (a) the measure of a ball does only depend on the radius $s$ and not on the
center $x$, so we simply denote $\omega(\overline{B}(x,s))$ by $\omega_{s}$.
These conditions are fulfilled when $X$ is a _homogeneous_ space, that is,
when the automorphism group acts transitively. Then the Haar measure of the
automorphism group induces an invariant probability measure on $X$ satisfying
(a) and (b).

The trivial lower bound above is known as the _volume bound_. Stronger and
more sophisticated lower bounds have not yet been established. The central aim
of this paper is to develop a semidefinite programming hierarchy for geometric
covering problems giving such lower bounds.

We start by motivating our definition of the covering hierarchy by recalling
the Lasserre hierarchy for general $0/1$ integer linear programs in Section 2.
Then we also recall the packing hierarchy of de Laat, Vallentin [9] in Section
3. The covering hierarchy is based on the packing hierarchy. We will define
our covering hierarchy in Section 4 and show its basic properties in Theorem
4.2, which is the principal result of the paper. In Section 5 we derive the
dual covering hierarchy and use the dual to show that for homogeneous compact
metric spaces the first step of the hierarchy collapses to the volume bound.

##  2\. The Lasserre hierarchy for $0/1$ integer linear programs

Consider the following integer linear program with $0/1$-variables

$\operatorname{ILP}=\min\\{c^{\sf T}x:x\in\\{0,1\\}^{n},\;Ax\geq b\\},$

where the matrix $A\in\mathbb{R}^{m\times n}$ and the vectors
$b\in\mathbb{R}^{m}$ and $c\in\mathbb{R}^{n}$ are given as input.

In the by now classical paper [14] Lasserre showed how to systematically
compute a sequence of stronger and stronger lower bounds, converging in $n+1$
steps to $\operatorname{ILP}$ by solving semidefinite programs of growing
size.

Lasserre’s original convergence proof relies on the Positivstellensatz of
Putinar [21] and on the flat extension theorem of Curto, Fialkow [8]. Laurent
[15] provided an elementary, combinatorial proof of the convergence. We shall
reproduce her arguments below because they gave the inspiration for the
semidefinite hierarchies for geometric packing and covering problems. For good
behavior we note that the results of Lasserre and Laurent are much more
general, as they apply to nonlinear (polynomial) optimization problems with
$0/1$-variables.

###  2.1. Combinatorial moment and localizing matrices

To define the Lasserre hierarchy for solving $\operatorname{ILP}$ we need a
bit of notation.

Set $X=[n]=\\{1,\ldots,n\\}$. We write $\mathcal{P}(X)$ for the power set of
$X$. By $\mathcal{P}_{t}(X)$ we denote the subsets of $\mathcal{P}(X)$
containing all $J\in\mathcal{P}(X)$ with $|J|\leq t$. For $t=0,\ldots,n$ and
$J\subseteq X$ we define the _(truncated) characteristic vector_
$\chi^{J}_{t}\in\\{0,1\\}^{\mathcal{P}_{t}(X)}$ by

$\chi^{J}_{t}(J^{\prime})=\begin{cases}1&\text{if $J^{\prime}\subseteq J$,}\\\
0&\text{otherwise.}\end{cases}$

A vector $y\in\mathbb{R}^{\mathcal{P}_{2t}(X)}$ defines the _(truncated)
combinatorial moment matrix_ $M_{t}(y)\in\mathcal{S}^{\mathcal{P}_{t}(X)}$,
which is a symmetric matrix with $\sum_{i=0}^{t}\binom{n}{i}$ many rows and
columns, by

$[M_{t}(y)]_{J,J^{\prime}}=y(J\cup J^{\prime}),\quad\text{ with
}J,J^{\prime}\in\mathcal{P}_{t}(X).$

The following lemma dealing with $t=n$, the final step of Lasserre’s
hierarchy, is crucial. It is due to Lindström [17] and Wilf [27].

######  Lemma 2.1.

A vector $y\in\mathbb{R}^{\mathcal{P}(X)}$ defines a positive semidefinite
combinatorial moment matrix $M_{n}(y)$ if and only if $y$ lies in the
(simplicial) polyhedral cone generated by the characteristic vectors
$\chi^{J}_{n}$, with $J\in\mathcal{P}(X)$. In short:

$M_{n}(y)\succeq 0\Longleftrightarrow
y\in\operatorname{cone}\\{\chi^{J}_{n}:J\in\mathcal{P}(X)\\}.$

###### Proof.

Sufficiency follows easily by the homomorphism property of the characteristic
vectors, which is

$\chi^{J}_{n}(J^{\prime}\cup
J^{\prime\prime})=\chi^{J}_{n}(J^{\prime})\cdot\chi^{J}_{n}(J^{\prime\prime})\;\text{
for all }\;J,J^{\prime},J^{\prime\prime}\in\mathcal{P}(X).$

Now any $y$ with

$y=\sum_{J\in\mathcal{P}(X)}\alpha_{J}\chi^{J}_{n}\;\text{ and
}\;\alpha_{J}\geq 0$

defines a positive semidefinite combinatorial moment matrix

$M_{n}(y)=\sum_{J\in\mathcal{P}(X)}\alpha_{J}\chi^{J}_{n}(\chi^{J}_{n})^{\sf
T}.$

For necessity, we first note that the characteristic vectors $\chi^{J}_{n}$
form a basis of $\mathbb{R}^{\mathcal{P}(X)}$. Let $\psi_{n}^{J}$ be the dual
basis with respect to the standard inner product, so that

$(\chi^{J}_{n})^{\sf
T}\psi^{J^{\prime}}_{n}=\delta_{J,J^{\prime}},\quad\text{where}\quad\delta_{J,J^{\prime}}=\begin{cases}1&\text{
if }J=J^{\prime}\\\ 0&\text{ otherwise.}\end{cases}$

Now consider a vector $y\in\mathbb{R}^{\mathcal{P}(X)}$ which defines a
positive semidefinite combinatorial moment matrix $M_{n}(y)$. Expand

$y=\sum_{J\in\mathcal{P}(X)}\alpha_{J}\chi^{J}_{n},$

and so

$0\leq(\psi^{J}_{n})^{\sf T}M_{n}(y)\psi^{J}_{n}=\alpha_{J}.\qed$

Consider the $j$-th row of the system $Ax\geq b$ which is the constraint
$a_{j}^{\sf T}x\geq b_{j}$, where the $j$-th row $a_{j}$ of matrix $A$ is
viewed as a column vector. Using this information we can define the $j$-th
_(truncated) localizing matrix_ $M^{j}_{t}(y)$ of
$y\in\mathbb{R}^{\mathcal{P}_{2t+2}(X)}$ by

$[M^{j}_{t}(y)]_{J,J^{\prime}}=\sum_{i\in X}a_{ji}y(J\cup
J^{\prime}\cup\\{i\\})-b_{j}y(J\cup J^{\prime}),$

where $J,J^{\prime}\in\mathcal{P}_{t}(X)$111In fact, the entries of $y$ which
are indexed by $2t+2$-element subsets of $X$ are not used here. We keep them
because the notation for the Lasserre hierarchy becomes simpler..

###  2.2. The Lasserre hierarchy for $\operatorname{ILP}$

For $t=1,\ldots,n$, the _$t$ -th step of the Lasserre hierarchy_ for
$\operatorname{ILP}$ is the (value of the) following semidefinite program

$\begin{split}\operatorname{las}_{t}=\min\Big{\\{}\sum_{i\in
X}c_{i}y(\\{i\\})\;:\;&y\in\mathbb{R}^{\mathcal{P}_{2t}(X)},\;y(\emptyset)=1,\\\\[-12.91663pt]
&M_{t}(y)\succeq 0,\;M^{j}_{t-1}(y)\succeq 0\;(j\in[m])\Big{\\}}.\end{split}$

The Lasserre hierarchy provides a monotonically increasing sequence of lower
bounds for $\operatorname{ILP}$:

$\operatorname{ILP}\geq\operatorname{las}_{n+1}\geq\operatorname{las}_{n}\geq\ldots\geq\operatorname{las}_{1}.$

The sequence is monotonically increasing because every feasible solution
$y\in\mathbb{R}^{\mathcal{P}_{2t}(X)}$ of $\operatorname{las}_{t}$ can be
truncated to a feasible solution
$y^{\prime}\in\mathbb{R}^{\mathcal{P}_{2t-2}(X)}$ of
$\operatorname{las}_{t-1}$ because $M_{t-1}(y^{\prime})$ and
$M^{j}_{t-2}(y^{\prime})$ are principal submatrices of $M_{t}(y)$ and
$M^{j}_{t-1}(y)$.

We have $\operatorname{ILP}\geq\operatorname{las}_{n+1}$ because if
$x^{*}\in\\{0,1\\}^{n}$ is an optimal solution of $\operatorname{ILP}$, then
$y=\chi^{J}_{n}$ with $J=\\{i\in X:x^{*}_{i}=1\\}$ is feasible for
$\operatorname{las}_{n+1}$; Positive semidefiniteness of $M_{n}(y)$ follows
from Lemma 2.1 and positive semidefiniteness of $M_{n}^{j}(y)$ is again due to
the homomorphism property of the characteristic vector

$\begin{split}[M^{j}_{n}(y)]_{J^{\prime},J^{\prime\prime}}&\;=\;\sum_{i\in
X}a_{ji}\chi^{J}_{n}(J^{\prime}\cup
J^{\prime\prime}\cup\\{i\\})-b_{j}\chi^{J}_{n}(J^{\prime}\cup
J^{\prime\prime})\\\ &\;=\;\chi^{J}_{n}(J^{\prime}\cup
J^{\prime\prime})\left(\sum_{i\in
X}a_{ji}\chi^{J}_{n}(\\{i\\})-b_{j}\right)\\\
&\;=\;\chi^{J}_{n}(J^{\prime}\cup J^{\prime\prime})\left(\sum_{i\in
X}a_{ji}x^{*}_{i}-b_{j}\right),\end{split}$

and hence

$M^{j}_{n}(y)=\left(a_{j}^{\sf
T}x^{*}-b_{j}\right)\chi^{J}_{n}(\chi^{J}_{n})^{\sf T}\succeq 0,$

because $a_{j}^{\sf T}x^{*}\geq b_{j}$.

Moreover, the Lasserre hierarchy converges to $\operatorname{ILP}$ in (at
most) $n+1$ steps because the reverse inequality
$\operatorname{ILP}\leq\operatorname{las}_{n+1}$ holds. This can be seen by
again applying Lemma 2.1, which says that we can expand any feasible solution
$y$ of $\operatorname{las}_{n+1}$ as
$y=\sum_{J\in\mathcal{P}(X)}\alpha_{J}\chi^{J}_{n}$ with nonnegative
coefficients $\alpha_{J}$. If $\alpha_{J}>0$, then $x^{J}\in\\{0,1\\}^{n}$
with $x^{J}_{i}=\chi^{J}_{n}(\\{i\\})$ is a feasible solution of
$\operatorname{ILP}$. This follows from the positive semidefiniteness of the
localizing matrix. In particular, using the dual basis $\psi^{J}_{n}$,

$0\leq(\psi^{J}_{n})^{\sf
T}M^{j}_{n}(y)\psi^{J}_{n}=\alpha_{J}\left(\sum_{i\in
X}a_{ji}\chi^{J}_{n}(\\{i\\})-b_{j}\right)$

holds, which implies $a_{j}^{\sf T}x^{J}\geq b_{j}$. The normalization
$y(\\{\emptyset\\})=1$ translates into $\sum_{J\in\mathcal{P}(X)}\alpha_{J}=1$
and therefore the objective value of $\operatorname{las}_{n+1}$ satisfies

$\sum_{i\in X}c_{i}y(\\{i\\})=\sum_{i\in
X}c_{i}\sum_{J\in\mathcal{P}(X)}\alpha_{J}\chi^{J}_{n}(\\{i\\})=\sum_{J\in\mathcal{P}(X)}\alpha_{J}c^{\sf
T}x^{J}\geq\operatorname{ILP}.$

##  3\. SDP hierarchy for geometric packing problems

Let $X$ be a compact metric space with distance function $d$. By
$B(x,r)=\\{y\in X:d(x,y)<r\\}$ we denote open metric balls with radius $r$ and
center $x$.

One important geometric parameter of $X$ and a positive $r$ is the _packing
number_

$\alpha(X,r)=\max\\{|Y|:Y\subseteq X:B(x,r)\cap B(y,r)=\emptyset\text{ for all
}x,y\in Y,x\neq y\\}.$

The idea behind the paper [9] of de Laat and Vallentin is to consider
$\alpha(X,r)$ as an infinite integer linear program where every point in $X$
corresponds to a $0/1$-variable. Then an appropriate semidefinite programming
hierarchy is constructed which can be used to determine upper bounds for
$\alpha(X,r)$ and which eventually converges to $\alpha(X,r)$. In this section
we recall the main steps of [9] because our semidefinite hierarchy for
covering builds on this packing hierarchy. Whereas the packing hierarchy only
uses moment constraints, the covering hierarchy needs to incorporate
localizing constraints.

The packing number can also be seen as the independence number of the,
potentially infinite, packing graph $P(X,r)$ with vertex set $X$ in which two
distinct vertices $x$, $y$ are adjacent whenever $B(x,r)\cap
B(y,r)\neq\emptyset$. Generally, the _independence number_ of a graph is the
maximum cardinality of an independent set, where a subset of the vertex set is
called an _independent set_ if it does not contain a pair of adjacent
vertices.

For a finite graph $G=(V,E)$, with vertex set $V=\\{1,\ldots,n\\}$ and edge
set $E$, one can formulate the independence number of $G$ as an integer linear
program with $0/1$-variables, which is

$\alpha(G)=\max\left\\{\sum_{i=1}^{n}x_{i}:x\in\\{0,1\\}^{n},x_{i}+x_{j}\leq
1\text{ for all }\\{i,j\\}\in E\right\\},$

and apply the Lasserre hierarchy.

Laurent [15, Lemma 20] observed that one can write the Lasserre hierarchy for
$\alpha(G)$ more compactly, only by considering combinatorial moment matrices,
without using localizing matrices. To state this compact version of the
Lasserre hierarchy, we slightly change the definitions introduced in Section
2. We hope that this will not cause confusion. The first change is that
instead of working with the complete power set of the vertex set we consider
only independent subsets. By $I_{t}$ we denote the set of all independent sets
with at most $t$ elements, then the $t$-th step of the Lasserre hierarchy is

(2)
$\operatorname{las}^{\alpha}_{t}(G)=\max\left\\{\sum_{i=1}^{n}y(\\{i\\}):y\in\mathbb{R}_{\geq
0}^{I_{2t}},\;y(\emptyset)=1,\;M_{t}(y)\succeq 0\right\\},$

where we define $M_{t}(y)\in\mathbb{R}^{I_{t}\times I_{t}}$ by

$[M_{t}(y)]_{J,J^{\prime}}=\begin{cases}y_{J\cup J^{\prime}}&\text{if $J\cup
J^{\prime}\in I_{2t}$,}\\\ 0&\text{otherwise},\end{cases}$

which is the second change. The third and last change, requiring $y$ to be a
nonnegative vector, enables us to say that the first step
$\operatorname{las}^{\alpha}_{1}(G)$ coincides with $\vartheta^{\prime}(G)$,
the strengthened version of Lovász $\vartheta$-number [18] due to Schrijver
[25]. We obtain

$\vartheta^{\prime}(G)=\operatorname{las}^{\alpha}_{1}(G)\geq\operatorname{las}^{\alpha}_{2}(G)\geq\ldots\geq\operatorname{las}^{\alpha}_{\alpha(G)}(G)=\alpha(G).$

In [9] this semidefinite programming hierarchy (2) is generalized to give a
hierarchy for the packing number $\alpha(X,r)$. In particular, independence
numbers of topological packing graphs are introduced, which include the
packings graphs $P(X,r)$ on compact metric spaces.

Since $X$ can have infinitely many points, some topology is needed to
generalize the objects in (2). The natural distance on nonempty subsets of $X$
is the Hausdorff distance

$d_{H}(J,J^{\prime})=\inf\\{\varepsilon:J\subseteq
J^{\prime}_{\varepsilon}\text{ and }J^{\prime}\subseteq J_{\varepsilon}\\},$

where $J_{\varepsilon}=\bigcup_{x\in J}B(x,\varepsilon)$ is the
$\varepsilon$-thickening of the set $J$.

Using the Hausdorff distance on $I_{t}$ instead of $\mathcal{P}_{t}(X)$ has an
important advantage. By considering $\alpha(X,r)$ we are interested in
cardinalities and generally elements in $\mathcal{P}_{t}(X)$ with non-equal
cardinality can be topologically close. However, because we work with $I_{t}$
and not with $\mathcal{P}_{t}(X)$, independent sets having different
cardinality, lie in separate connected components; see the discussion in [9,
Section 2].

In the generalization, the vector $y\in\mathbb{R}_{\geq 0}^{I_{2t}}$ is
replaced by a measure $\lambda\in\mathcal{M}(I_{2t})_{\geq 0}$ in the cone of
non-negative Radon measure. The idea is that an independent set $S$ determines
a feasible solution

$\lambda=\sum_{R\in I_{2t}:R\subseteq S}\delta_{R},\quad\text{where
$\delta_{R}$ is the delta measure at $R$,}$

of the $t$-th step of the packing hierarchy.

The map which assigns $y$ the truncated combinatorial moment matrix $y\mapsto
M_{t}(y)$ is replaced by a dual construction using the adjoint map.

By the Riesz representation theorem the dual space of the space of real-valued
continuous functions $\mathcal{C}(I_{2t})$, equipped with the supremum norm,
is the space of signed Radon measures $\mathcal{M}(I_{2t})$. The dual cone of
nonnegative continuous functions we denote by $\mathcal{M}(I_{2t})_{\geq 0}$.
Similarly, the dual space of symmetric, real-valued continuous kernels
$\mathcal{C}(I_{t}\times I_{t})_{\operatorname{sym}}$ is the space of
symmetric Radon measures $\mathcal{M}(I_{t}\times
I_{t})_{\operatorname{sym}}$. The dual cone of positive definite kernels, that
is kernels $K\in\mathcal{C}(I_{t}\times I_{t})_{\operatorname{sym}}$ which
satisfy

$(K(J_{i},J_{j}))_{i,j=1}^{m}\succeq 0\quad\text{ for all
}\;J_{1},\ldots,J_{m}\in I_{2t},\;m\in\mathbb{N},$

we denote by $\mathcal{M}(I_{t}\times I_{t})_{\succeq 0}$.

We define the map

$A_{t}:\mathcal{C}(I_{t}\times
I_{t})_{\operatorname{sym}}\to\mathcal{C}(I_{2t})\quad\text{by}\quad
A_{t}K(S)=\sum_{J,J^{\prime}\in I_{t}:J\cup J^{\prime}=S}K(J,J^{\prime}),$

where $K\in\mathcal{C}(I_{t}\times I_{t})_{\operatorname{sym}}$ and $S\in
I_{2t}$ Note that the above sum has at most $2^{2t}$ summands. Therefore, the
adjoint map

$A_{t}^{*}:\mathcal{M}(I_{2t})\to\mathcal{M}(I_{t}\times
I_{t})_{\operatorname{sym}},$

(well-)defined by

$\langle K,A^{*}\lambda\rangle=\langle A_{t}K,\lambda\rangle,$

is the natural replacement for $y\mapsto M_{t}(y)$.

After these preparations one can define the $t$-th step of the _packing
hierarchy_ by

$\operatorname{las}^{\alpha}_{t}(P(X,r))=\max\\{\lambda(I_{=1}):\lambda\in\mathcal{M}(I_{2t})_{\geq
0},\;\lambda(\\{\emptyset\\})=1,\;A_{t}^{*}(\lambda)\in\mathcal{M}(I_{t}\times
I_{t})_{\succeq 0},\\}$

where $I_{=1}$ denotes the set of independent subsets with cardinality exactly
$1$. Again, and this is the main result of [9],

$\vartheta^{\prime}(P(X,r))=\operatorname{las}^{\alpha}_{1}(P(X,r))\geq\operatorname{las}^{\alpha}_{2}(P(X,r))\geq\ldots\geq\operatorname{las}^{\alpha}_{\alpha(X,r)}(P(X,r))=\alpha(X,r)$

holds.

The first step coincides with the generalization of the
$\vartheta^{\prime}$-number for the graph $P(X,r)$, defined in [2]. If for
instance the compact metric space is the unit sphere, $X=S^{n-1}$, then the
first step coincides with the linear programming bound of Delsarte, Goethals,
Seidel [10].

The convergence follows from a Choquet-type variant (cf. Simon [26]) of the
crucial Lemma 2.1, where finite convex combinations are replaced by integrals
with respect to probability measures, which reads:

######  Lemma 3.1.

(de Laat, Vallentin [9, Proposition 1]) Let $I=I_{\alpha(X,r)}$ be the set of
all independent sets of $P(X,r)$. Let $\lambda\in\mathcal{M}(I)$ be so that
$\lambda(\\{\emptyset\\})=1$ and
$A_{\alpha(X,r)}^{*}\lambda\in\mathcal{M}(I\times I)_{\succeq 0}$. Then there
exists a unique probability measure $\sigma\in\mathcal{M}(I)_{\geq 0}$ so that
$\lambda$ can be represented as

$\lambda=\int\chi^{R}\,d\sigma(R),\quad\text{where}\quad\chi^{R}=\sum_{Q\subseteq
R}\delta_{Q}.$

Next to putting the linear programming bound into perspective and giving
theoretical convergence, the packing hierarchy has turned out to be useful in
various applications, especially for the unit sphere or for Euclidean space
where the presence of symmetries makes it possible to simplify the
computations. Bachoc, Vallentin [1] used semidefinite constraints from
$\operatorname{las}^{\alpha}_{2}$ to find new upper bounds for the kissing
number. de Laat [11] used the second step of the hierarchy in the context of
energy minimization on the sphere $S^{2}$. de Laat, Machado, de Munick Keizer
[12] computed $\operatorname{las}^{\alpha}_{2}$ and
$\operatorname{las}^{\alpha}_{3}$ for the problem of equiangular lines; they
were even able to turn these computations in an asymptotic analysis. Cohn,
Salmon [6] showed that the packing hierarchy converges to the packing density
for Euclidean space. Cohn, de Laat, Salmon [5] used constraints from
$\operatorname{las}^{\alpha}_{2}$ to find new upper bounds for sphere packing
densities in dimensions $4$ through $7$ and $9$ through $16$.

##  4\. SDP hierarchy for geometric covering problems

The finite graph analog of the covering number is the domination number. For a
finite graph $G=(V,E)$, with vertex set $V=\\{1,\ldots,n\\}$ and edge set $E$
a subset of the vertex set $D\subseteq V$ is called a _dominating set_ if for
every vertex $i\in V$ either the vertex lies itself in the dominating set or
there is vertex $j\in D$, in the dominating set, which is adjacent to $i$. The
_domination number_ $\gamma(G)$ of $G$ is the cardinality of a smallest
dominating set. One can formulate $\gamma(G)$ as an integer linear program
with $0/1$-variables:

$\gamma(G)=\min\left\\{\sum_{i=1}^{n}x_{i}:x\in\\{0,1\\}^{n},\sum_{i\in
V:\\{i,j\\}\in E}x_{i}\geq 1\;(j\in V)\right\\},$

and apply the Lasserre hierarchy. Here the $t$-th step of the Lasserre
hierarchy is

$\begin{split}\operatorname{las}^{\gamma}_{t}(G)=\min\Big{\\{}\sum_{i=1}^{n}y(\\{i\\})\;:\;&y\in\mathbb{R}^{\mathcal{P}_{2t}(V)},y(\emptyset)=1,\\\\[-12.91663pt]
&M_{t}(y)\succeq 0,\;M^{j}_{t-1}(y)\succeq 0\;(j\in V)\Big{\\}}\end{split}$

where the linear constraint that every vertex $j\in V$ either should lie in
the dominating set or should be adjacent to a vertex in the dominating set
determines a truncated localizing matrix

$[M^{j}_{t-1}(y)]_{J,J^{\prime}}=\sum_{i\in V:\\{i,j\\}\in E}y(J\cup
J^{\prime}\cup\\{i\\})-y(J\cup J^{\prime}),$

where $J,J^{\prime}\in\mathcal{P}_{t-1}(V)$.

In the geometric setting we consider the covering graph $C(X,r)$ with vertex
set $X$ in which two vertices $x,y\in X$ are adjacent whenever $d(x,y)\leq r$.
Then, as dominating sets in $C(X,r)$ determine the centers of balls with
radius $r$ of a covering of $X$, and vice versa, we have
$\gamma(C(X,r))=\mathcal{N}(X,r)$.

We want to define a semidefinite hierarchy which converges in finitely many
steps to the covering number $\mathcal{N}(X,r)$. For the proof we will make
use of Lemma 3.1. Therefore, we have to assume that we know a lower bound
$\varepsilon>0$ so that an optimal covering $X$ determines a packing of balls
with radius $\varepsilon$. Clearly such a positive lower bound always exists
as optimal coverings consist of finitely many pairwise distinct balls. We
define $I_{t}$ to be the set of subsets of $X$ with at most $t$ elements which
are independent in the packing graph $P(X,\varepsilon)$.

For $y\in X$ we define the map

$B^{y}_{t}:\mathcal{C}(I_{t}\times
I_{t})_{\operatorname{sym}}\to\mathcal{C}(I_{2t+2})$

by

$B^{y}_{t}K(S)=\sum_{x\in\overline{B}(y,r),J,J^{\prime}:J\cup
J^{\prime}\cup\\{x\\}=S}K(J,J^{\prime})-\sum_{J,J^{\prime}\in I_{t}:J\cup
J^{\prime}=S}K(J,J^{\prime}),$

where $K\in\mathcal{C}(I_{t}\times I_{t})_{\operatorname{sym}}$ and $S\in
I_{2t+2}$. The adjoint map
$(B^{y}_{t})^{*}:\mathcal{M}(I_{2t+2})\to\mathcal{M}(I_{t}\times
I_{t})_{\operatorname{sym}}$ gives the analog of the map which assigns $y$ to
the truncated combinatorial moment matrix.

######  Definition 4.1.

For $t=1,2,\ldots,$ we define the $t$-th step of the _covering hierarchy_ by

$\begin{split}\operatorname{las}^{\gamma}_{t}(C(X,r))=\inf\Big{\\{}\lambda(I_{=1})\;:\;&\lambda\in\mathcal{M}(I_{2t})_{\geq
0},\;\lambda(\\{\emptyset\\})=1,\\\
&A_{t}^{*}(\lambda)\in\mathcal{M}(I_{t}\times I_{t})_{\succeq 0},\\\
&(B^{y}_{t-1})^{*}(\lambda)\in\mathcal{M}(I_{t-1}\times I_{t-1})_{\succeq
0}\;(y\in X)\Big{\\}}.\end{split}$

######  Theorem 4.2.

The covering hierarchy gives a monotonically increasing sequence of lower
bounds for the covering number and converges to the covering number in at most
$\alpha(P(X,\varepsilon))$ steps:

$\operatorname{las}^{\gamma}_{1}(C(X,r))\leq\operatorname{las}^{\gamma}_{2}(C(X,r))\leq\ldots\leq\operatorname{las}^{\gamma}_{\alpha(P(X,\varepsilon))}(C(X,r))=\mathcal{N}(X,r).$

We split the proof of this theorem in three lemmas.

###  4.1. Every step of the covering hierarchy gives a lower bound for the
covering number.

######  Lemma 4.3.

For every $t=1,2,\ldots$ the inequality
$\operatorname{las}^{\gamma}_{t}(C(X,r))\leq\mathcal{N}(X,r)$ holds.

###### Proof.

We verify this inequality by showing that every finite covering $Y$ of $X$
gives a feasible solution

$\lambda=\sum_{Z\in I_{2t}:\ Z\subseteq Y}\delta_{Z}$

of the $t$-step of the covering hierarchy with objective
$\lambda(I_{=1})=|Y|$.

Indeed, we have

$\lambda\left(\\{\emptyset\\}\right)=\sum_{Z\in I_{2t}:Z\subseteq
Y}\delta_{Z}\left(\\{\emptyset\\}\right)=\delta_{\emptyset}\left(\\{\emptyset\\}\right)=1.$

Then, for every $K\in\mathcal{C}(I_{t}\times I_{t})_{\succeq 0}$:

$\begin{split}\langle
A_{t}^{*}\lambda,K\rangle&=\langle\lambda,A_{t}K\rangle\\\ &=\sum_{Z\in
I_{2t}:Z\subseteq Y}\sum_{J,J^{\prime}\in I_{t}:Z=J\cup
J^{\prime}}K(J,J^{\prime})\\\ &=\sum_{J,J^{\prime}\in
I_{t}:J,J^{\prime}\subseteq Y}K(J,J^{\prime})\\\ &\geq 0,\end{split}$

as well as, for every $y\in X$ and every
$K^{\prime}\in\mathcal{C}(I_{t-1}\times I_{t-1})_{\succeq 0}$

$\begin{split}&\langle(B_{t-1}^{y})^{*}\lambda,K^{\prime}\rangle\\\
=\;&\langle\lambda,B_{t-1}^{y}K^{\prime}\rangle\\\ =\;&\sum_{Z\in
I_{2t}:Z\subseteq Y}\Big{(}\sum_{x\in\overline{B}(y,r),\ J,J^{\prime}:Z=J\cup
J^{\prime}\cup\\{x\\}}K^{\prime}(J,J^{\prime})-\sum_{J,J^{\prime}:Z=J\cup
J^{\prime}}K^{\prime}(J,J^{\prime})\Big{)}\\\ =\;&\sum_{x\in
Y\cap\overline{B}(y,r)}\sum_{J,J^{\prime}:\ J,J^{\prime}\subseteq
Y}K^{\prime}(J,J^{\prime})-\sum_{J,J^{\prime}:J,J^{\prime}\subseteq
Y}K^{\prime}(J,J^{\prime})\\\
=\;&(|Y\cap\overline{B}(y,r)|-1)\sum_{J,J^{\prime}\in
I_{t-1}:J,J^{\prime}\subseteq Y}K^{\prime}(J,J^{\prime})\\\
\geq\;&0.\end{split}$

where the last inequality is implied by the fact that
$Y\cap\overline{B}(y,r)\neq\emptyset$ since $Y$ is a covering. ∎

###  4.2. The covering hierarchy is monotonically increasing with $t$.

######  Lemma 4.4.

For every $t=1,2,\ldots$ the inequality
$\operatorname{las}^{\gamma}_{t}(C(X,r))\leq\operatorname{las}^{\gamma}_{t+1}(C(X,r))$
holds.

###### Proof.

Increasing $t$ strengthens the bound by imposing more constraints to the set
of feasible solutions. To be precise, if the measure
$\lambda\in\mathcal{M}(I_{2t+2})_{\geq 0}$ is feasible for
$\operatorname{las}^{\gamma}_{t+1}(C(X,r))$, then its restriction to
$\mathcal{M}(I_{2t})$ is also feasible for
$\operatorname{las}^{\gamma}_{t}(C(X,r))$. Furthermore, $\lambda$ and its
restriction have the same objective value, namely $\lambda(I_{=1})$. ∎

###  4.3. The covering hierarchy converges to the covering number.

Before we can prove this, we need a technical, topological observation.

We equip the non-empty sets in $I_{t}$ with the _Hausdorff distance_

$d_{H}(Y,Z)=\max\left\\{\sup_{y\in Y}\inf_{z\in Z}d(y,z),\sup_{z\in
Z}\inf_{y\in Y}d(y,z)\right\\}$

and extend this distance to a metric

$d_{H}(Y,Z)=\begin{cases}d_{H}(Y,Z)&\text{ if }Y,Z\neq\emptyset\\\ 0&\text{ if
}Y=Z=\emptyset\\\ \sup_{x,y\in X}d(x,y)&\text{ otherwise,}\end{cases}$

which also takes care of $\emptyset\in I_{t}$.

######  Lemma 4.5.

Let $B=\overline{B}(x,r)$ be a ball in $X$. Consider the function
$k:I_{t}\to\mathbb{R}$ defined by

$k(J)=\begin{cases}(-1)^{|J|}&\text{ if }J\subseteq B\\\ 0&\text{
otherwise}.\end{cases}$

Then there exists a continuous function $g\in\mathcal{C}(I_{t})$ such that $k$
and $g$ agree $\nu$-almost surely for every $\nu\in\mathcal{M}(I_{t})$.

###### Proof.

First we observe that one can write $k$ in terms of indicator functions

$\displaystyle k(J)$ $\displaystyle=\left(\sum_{r=0,\ r\text{
even}}^{|J|}\mathbf{1}_{I_{=r}}(J)-\sum_{r=0,\ r\text{
odd}}^{|J|}\mathbf{1}_{I_{=r}}(J)\right)\mathbf{1}_{B}(J).$

Due to the continuity of $\mathbf{1}_{I_{=r}}$, given by [9, Lemma 2], it
suffices to show that there is a continuous function $g$ such that
$g(J)=\mathbf{1}_{B}(J)$, $\nu$-almost surely.

We further consider $\\{J\in I_{t}:J\nsubseteq B\\}$ and show that it is an
open set in $I_{t}$. Because $J\nsubseteq B$, implying $J\neq\emptyset$, there
is an element $y_{0}\in J\setminus B$. Due to the Hausdorff property of $X$ we
have $d(y_{0},b)>\delta$ for every $b\in B$. Thus we can consider the ball
$B(J,\delta)$ defined by the Hausdorff metric and show that
$d_{H}(B,B(J,\delta))\geq\sup_{y\in B(J,\delta)}\inf_{b\in
B}d(b,y)\geq\inf_{b\in B}d(b,y_{0})>0$ holds. This implies that
$B(J,\delta)\subseteq\\{J\in I_{t}:\ J\nsubseteq B\\}$ and thus

$C=\\{J\in I_{t}:\ J\nsubseteq B\\}\text{ is open and }D=\\{J\in I_{t}:\
J\subseteq B\\}\text{ is closed.}$

As a metric space $(I_{t},d_{H})$ is a normal space and thus we can apply
Urysohn’s lemma, which gives us that for any compact subset of $C$, say
$C^{\prime}$ and $D$ there exists a continuous function $g$ with $g(c)=0$ for
every $c\in C^{\prime}$ and $g(d)=1$ for every $d\in D$. In the case of our
metric space $(I_{t},d_{H})$ one concrete $g$ that satisfies the constraints
can be shown to be
$g(J)=\frac{d_{H}(J,C^{\prime})}{d_{H}(J,C^{\prime})+d_{H}(J,D)}$. This $g$ is
bounded by $0$ and $1$. For an arbitrary Radon measure
$\nu\in\mathcal{M}(I_{t})$ and every compact $C^{\prime}\subseteq C$ we
consider

$\int_{I_{t}}|\mathbf{1}_{B}-g|d\nu=\int_{C\setminus
C^{\prime}}|\mathbf{1}_{B}-g|d\nu\leq\nu(C\setminus C^{\prime}).$

Thus

$\int_{I_{t}}|\mathbf{1}_{B}-g|d\nu\leq\inf_{C^{\prime}\subseteq C,\
C^{\prime}\text{ compact}}\nu(C\setminus
C^{\prime})\leq\nu(C)-\sup_{C^{\prime}\subseteq C,\ C^{\prime}\text{
compact}}\nu(C^{\prime})=0,$

where the last step is due to the inner regularity of every Radon measure
$\nu$. ∎

######  Lemma 4.6.

Equality
$\operatorname{las}^{\gamma}_{\alpha(P(X,\varepsilon))}(C(X,r))=\mathcal{N}(X,r)$
holds.

###### Proof.

Set $\alpha=\alpha(P(X,\varepsilon))$ We consider a feasible measure $\lambda$
for the program $\operatorname{las}^{\gamma}_{\alpha}(C(X,r))$ and its
representation $\lambda=\int\chi_{R}\,d\sigma(R)$, which exists due to Lemma
3.1.

Now we have to verify that $\sigma$-supported subsets $R\subseteq X$ determine
a covering. For contradiction, suppose $R$ does not determine a covering. Then
there exists $y\in X$ so that $\overline{B}(y,r)\cap R=\emptyset$. Consider
the map $k:I_{\alpha}\to\mathbb{R}$, with $k(J)=(-1)^{|J|}$ if
$J\subseteq\overline{B}(y,r)$ and $k(J)=0$ otherwise, as defined in Lemma 4.5
and let $g$ be its continuous version. Then

$\begin{split}0\;\leq\;&\langle(B^{y}_{\alpha})^{*}\chi_{R},g\otimes
g\rangle\\\ \;=\;&\chi^{R}(B^{y}_{\alpha}(g\otimes g))\\\
\;=\;&\sum_{x\in\overline{B}(y,r),J,J^{\prime}:J\cup
J^{\prime}\cup\\{x\\}\subseteq R}g\otimes
g(J,J^{\prime})-\sum_{J,J^{\prime}\in I_{t}:J\cup J^{\prime}\subseteq
R}g\otimes g(J,J^{\prime}).\\\ \;=\;&|\overline{B}(y,r)\cap
R|\sum_{J,J^{\prime}:J\cup J^{\prime}\cup\subseteq R}g\otimes
g(J,J^{\prime})-\sum_{J,J^{\prime}\in I_{t}:J\cup J^{\prime}\subseteq
R}g\otimes g(J,J^{\prime})\\\ \;=\;&-\sum_{J,J^{\prime}\in I_{t}:J\cup
J^{\prime}\subseteq R}g\otimes g(J,J^{\prime})\\\
\;=\;&-\left(\sum_{J:J\subseteq\overline{B}(y,r)\cap
R}(-1)^{|J|}\right)^{2}\\\ \;=\;&-1.\end{split}$

We finish the proof of the lemma by looking at the objective value of
$\lambda$ which is

$\lambda(I_{=1})=\int\chi_{R}(I_{=1})\,d\sigma(R)=\int|R|\,d\sigma(R)\geq\int\mathcal{N}(X,r)\,d\sigma(R)=\mathcal{N}(X,r),$

because every $R$ in the support of $\sigma$ determines a covering and
$\sigma$ is a probability measure. ∎

##  5\. The dual covering hierarchy

In this section we assume that the automorphism group $G$ of $X$ acts
transitively on $X$ so that $X$ is the homogenous space $G/H$ where $H$ is the
stabilizer subgroup of a point in $G$. This is a natural assumption which is
fulfilled in many examples; for example when $X$ is the unit sphere $S^{n-1}$
and $G$ is the orthogonal group $\mathrm{O}(n)$ and $H$ is isomorphic to
$\mathrm{O}(n-1)$. Then the Haar measure of $G$ induces a probability measure
$\omega$ on $G/H$ which satisfies conditions (a) and (b) given in Section 1.

Looking at the covering hierarchy this has the advantage, due to convexity,
that the constraints coming from the localizing matrix only have to required
for one arbitrary point of $X$. Let $e\in X$ be this point, then

$\begin{split}\operatorname{las}^{\gamma}_{t}(C(X,r))=\inf\Big{\\{}\lambda(I_{=1})\;:\;&\lambda\in\mathcal{M}(I_{2t})_{\geq
0},\;\lambda(\\{\emptyset\\})=1,\\\
&A_{t}^{*}(\lambda)\in\mathcal{M}(I_{t}\times I_{t})_{\succeq 0},\\\
&(B^{e}_{t-1})^{*}(\lambda)\in\mathcal{M}(I_{t-1}\times I_{t-1})_{\succeq
0}\Big{\\}}.\end{split}$

We define the $t$-th step of the dual covering hierarchy by

$\begin{split}\operatorname{las}^{\gamma,*}_{t}(C(X,r))=\sup\Big{\\{}y\;:\;&y\in\mathbb{R},\\\\[-4.30554pt]
&\mathbf{1}_{I_{=1}}(S)-y\mathbf{1}_{\\{\emptyset\\}}(S)-A_{t}K(S)-B_{t-1}^{e}K^{\prime}(S)\geq
0\\\ &\qquad\text{ for all }S\in I_{2t},\\\\[-4.30554pt]
&K\in\mathcal{C}(I_{t}\times I_{t})_{\succeq 0},\
K^{\prime}\in\mathcal{C}(I_{t-1}\times I_{t-1})_{\succeq
0}\Big{\\}}.\end{split}$

One can easily check that weak duality
$\operatorname{las}^{\gamma,*}_{t}\leq\operatorname{las}^{\gamma}_{t}$ holds.
Although we do not need this here, we note that also strong duality holds;
this was shown by Rolfes in [24] using the framework of infinite dimensional
conic optimization presented in Barvinok [3, Chapter IV].

With the help of the dual covering hierarchy
$\operatorname{las}_{t}^{\gamma,*}$ it is further possible to show that the
first step of the hierarchy coincides with the volume bound.

######  Theorem 5.1.

If the automorphism group $G$ acts transitively on $X$, then the first step of
the covering hierarchy collapses to the volume bound,

$\operatorname{las}^{\gamma,*}_{1}(C(X,r))=\frac{1}{\omega_{r}}.$

###### Proof.

Consider a probability measure $\omega$ satisfying properties (a) and (b).
Then, if $t=1$, we observe that the measure

$\lambda(\mathcal{S})=\begin{cases}1&\text{ if
}\mathcal{S}=\\{\emptyset\\},\\\
\frac{\omega\left(\bigcup_{\\{x\\}\in\mathcal{S}}\\{x\\}\right)}{\omega_{r}}&\text{
if }\mathcal{S}\subseteq I_{=1},\\\ 0&\text{ otherwise.}\end{cases}$

is a feasible measure for $\operatorname{las}^{\gamma}_{1}(C(X,r))$. Its
objective value is $\lambda(I_{=1})=\frac{1}{\omega_{r}}$ and thus implies
$\operatorname{las}^{\gamma}_{1}(C(X,r))\leq\frac{1}{\omega_{r}}$.

For the reverse inequality we have

$B_{0}^{e}K^{\prime}(\emptyset)=-K^{\prime}(\emptyset,\emptyset),$

and

$\displaystyle B_{0}^{e}K^{\prime}\left(\\{z\\}\right)$
$\displaystyle=\sum_{x\in\overline{B}(e,r):\
\\{x\\}=\\{z\\}}K^{\prime}(\emptyset,\emptyset)$
$\displaystyle=\begin{cases}K^{\prime}(\emptyset,\emptyset)&\text{ if
}z\in\overline{B}(e,r)\\\ 0&\text{ otherwise,}\end{cases}$

and

$B_{0}^{e}K^{\prime}\left(\\{z_{1},z_{2}\\}\right)=\sum_{x\in\overline{B}(e,r):\
\\{x\\}=\\{z_{1},z_{2}\\}}K^{\prime}(\emptyset,\emptyset)=0.$

Thus,

$K=0,\;K^{\prime}(\emptyset,\emptyset)=\frac{1}{\omega_{r}}\;\text{ and
}\;y=K^{\prime}(\emptyset,\emptyset)$

is a feasible solution for $\operatorname{las}_{1}^{\gamma,*}(C(X,r))$. So
$\operatorname{las}^{\gamma,*}_{1}(C(X,r))\geq\frac{1}{\omega_{r}}$ and by
weak duality
$\operatorname{las}^{\gamma}_{1}(C(X,r))\geq\frac{1}{\omega_{r}}$. ∎

For the packing number $\alpha(S^{n-1},r)$ for the unit sphere, the first step
of the packing hierarchy $\operatorname{las}^{\alpha}_{1}(P(S^{n-1},r))$
coincides with the linear programming bound $\vartheta^{\prime}(P(S^{n-1},r))$
of Delsarte, Goethals, Seidel, which often provides strong and sometimes even
tight upper bounds. Now Theorem 5.1 gives an explanation why the corresponding
first step of the covering hierarchy
$\operatorname{las}^{\gamma}_{1}(C(S^{n-1},r))$, which also is, after symmetry
reduction, a linear programming bound, is not a strong bound for the covering
number. On the other hand, the first step of the dual covering hierarchy is
implicitly used in the analysis of the greedy approach to construct efficient
coverings, see [23].

## Acknowledgements

The authors are grateful to David de Laat for helpful discussions. The first
author was supported by the Tromsø Research Foundation project “Symmetry in
Real Algebraic Geometry” and the UiT Aurora project MASCOT. The second author
was supported by a ”Short-Term Grant” funded by DAAD. The third named author
is partially supported by the SFB/TRR 191 “Symplectic Structures in Geometry,
Algebra and Dynamics” funded by the DFG.

## References

  * [1] C. Bachoc, F. Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc. 21 (2008), 909–924.
  * [2] C. Bachoc, G. Nebe, F.M. de Oliveira Filho, F. Vallentin, Lower bounds for measurable chromatic numbers, Geom. Funct. Anal. 19 (2009), 645–661.
  * [3] A. Barvinok, A course in convexity, AMS, 2002.
  * [4] S.V. Borodachov, D.P. Hardin, E.B. Saff, Discrete energy on rectifiable sets, Springer, 2019.
  * [5] H. Cohn, D. Laat, A. Salmon, Three-point bounds for sphere packing, arXiv:2206.15373 [math.MG]
  * [6] H. Cohn, A. Salmon, Sphere packing bounds via rescaling, arXiv:2108.10936 [math.MG]
  * [7] F. Cucker, S. Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc. 39 (2002), 1–49.
  * [8] R.E. Curto, L.A. Fialkow, The truncated complex $K$-moment problem, Trans. Amer. Math. Soc. 352 (2000), 2825–2855.
  * [9] D. de Laat, F. Vallentin, A semidefinite programming hierarchy for packing problems in discrete geometry, Math. Program., Ser. B 151 (2015), 529–553.
  * [10] P. Delsarte, J.M. Goethals, J.J. Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977), 363–388.
  * [11] D. de Laat, Moment methods in energy minimization: New bounds for Riesz minimal energy problems, Trans. Amer. Math. Soc. 373 (2020), 1407–1453
  * [12] D. de Laat, F Caluza Machado, W. de Muinck Keizer, The Lasserre hierarchy for equiangular lines with a fixed angle, arXiv:2211.16471 [math.MG]
  * [13] S. Foucart, H. Rauhut, A mathematical introduction to compressive sensing, Birkhäuser/Springer, 2013.
  * [14] J.B. Lasserre, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM J. Optim. 12 (2002), 756–769.
  * [15] M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res. 28 (2003), 470–496.
  * [16] M. Ledoux, M. Talagrand, Probability in Banach spaces, Springer, 1991.
  * [17] B. Lindström, Determinants on semilattices, Proc. Amer. Math. Soc. 20 (1969) 207–208.
  * [18] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inf. Th. 25 (1979), 1–7.
  * [19] M. Naszódi, Flavors of Translative Coverings, pp. 335–358 in: New Trends in Intuitive Geometry, Springer, 2018.
  * [20] M.A. Nielsen, I.L. Chuang, Quantum computation and quantum information, Cambridge University Press, 2000.
  * [21] M. Putinar, Positive polynomials on compact semi-algebraic sets, Ind. Univ. Math. J. 42 (1993), 969–984.
  * [22] C.A. Rogers, Packing and covering, Cambridge University Press, 1964.
  * [23] J.H. Rolfes, F. Vallentin, Covering compact metric spaces greedily, Acta Math. Hungar. 155 (2018), 130–140.
  * [24] J.H. Rolfes, Convex optimization techniques for geometric covering problems, PhD thesis, University of Cologne, 2019.
  * [25] A. Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inf. Th. 25 (1979), 425–429.
  * [26] B. Simon, Convexity: An analytic viewpoint, Cambridge University Press, 2011
  * [27] H.S. Wilf, Hadamard determinants, Möbius functions, and the chromatic number of a graph, Bull. Amer. Math. Soc. 74 (1968) 960–964.


# Wired Perspectives: Multi-View Wire Art Embraces Generative AI

Zhiyu Qu1 Lan Yang2 Honggang Zhang2 Tao Xiang1 Kaiyue Pang1 Yi-Zhe Song1
1SketchX, CVSSP, University of Surrey 2Beijing University of Posts and
Telecommunications
{z.qu, t.xiang, k.pang<EMAIL_ADDRESS>{ylan<EMAIL_ADDRESS>
https://dreamwireart.github.io

###### Abstract

Creating multi-view wire art (MVWA), a static 3D sculpture with diverse
interpretations from different viewpoints, is a complex task even for skilled
artists. In response, we present DreamWire, an AI system enabling everyone to
craft MVWA easily. Users express their vision through text prompts or
scribbles, freeing them from intricate 3D wire organisation. Our approach
synergises 3D Bézier curves, Prim’s algorithm, and knowledge distillation from
diffusion models or their variants (_e.g_., ControlNet). This blend enables
the system to represent 3D wire art, ensuring spatial continuity and
overcoming data scarcity. Extensive evaluation and analysis are conducted to
shed insight on the inner workings of the proposed system, including the
trade-off between connectivity and visual aesthetics.

Figure 1: Multi-view art done generatively. We present DreamWire as the first
system that takes user prompt for each view as input – either via the
expressive vehicle of text or image – and produces 3D line sculptures showing
distinct interpretations when viewed at different angles, _i.e_., multi-view
wire art (MVWA). Each MVWA instance is created by optimising a set of randomly
initialised Bézier curves towards the visual matching objective of a universal
generative prior (diffusion models or ControlNet). Notably, the “GBE” here
pays tribute to the book “Gödel, Escher, Bach: an Eternal Golden Braid” [12],
which discusses how systems can acquire meaningful context despite being made
of “meaningless” elements, just like what MVWA does.

##  1 Introduction

A great thought begins by seeing something differently, with a shift of the
mind’s eye.

Albert Einstein

There is an artist in everyone, they say. Attending an art exhibition, being
mesmerised by a 3D wire-art installation from Matthieu Robert-
Ortis111https://leonacreo.com/sculptures-by-matthieu-robert-ortis/ is what
motivated this paper! As an AI practitioner, the immediate question was, “Can
I program this?” Not to replace artists, but rather, for fun, for finding that
artist within myself, and for the vision of democratising art creation for
everyone!

Lighthearted as it might sound, this endeavour holds scientific value on two
fronts. First, it delves into the uncharted territory of wired-art generation
using current generative AI [33, 38, 36], seeking to understand the limits of
these technologies in the realm of this unique artistic form. Secondly, it
contributes to the ongoing dialogue by exploring the expansion of existing
2D-focused generation methods into the intricate domains of 3D and perhaps
more challengingly, the extreme abstraction presented by wire art.

Multi-view wire art (MVWA) [14] is a unique form of art that leverages wire as
a flexible medium to create complex 3D objects, whereupon different
viewpoints, multiple interpretable images appear – recall those 2D pictures
where you move your head and see different things. This time, you are walking
around a 3D installation, and upon different viewing angles, you see different
2D depictions (see Fig. 1). Being prohibitively difficult for novice users,
creating MVWA is an extremely time-consuming task even for qualified artists.
Apart from artistic ideation, working with reverse projection (2D to 3D),
efforts have been made on physics so the installation does not collapse. Our
ambition for MVWA, one that focuses on democratising its creation for
everyone, is removing all said challenges but limiting its creation to just
ideation (perhaps not entirely artistic, though!). That is, specifying what
you want each view to look like, and bingo – the final 3D art form!

We present a system named DreamWire to do just that. All users need to
generate 3D wire art is a set of text prompts (_e.g_., “a portrait of
Einstein”) or rough scribbles (_e.g_., styled writings of “CVPR”), each for a
2D view. Fig. 1 illustrates some examples, and for a more immersive
experience, we offer fully interactive MVWA demos in the project page – please
do set your eyes on them; we promise they won’t be boring! However, there is a
caveat: there is an upper bound (three) on how many viewpoints an MVWA object
could support, largely due to the degree of conflict in the 3D wire space that
a large number of views would introduce.

Computational methods for MVWA [14] or related art forms alike [22] have been
attempted before but only appear as rule-based endeavours – they rely on a set
of prewritten rules to construct an MVWA piece222For readers unfamiliar with
the existing “assembly manual” for MVWA, we briefly summarise the rules here:
i) back-project the 2D images to 3D via generalised cones and discrete the
intersection of the camera’s viewing frustums with a fixed resolution of
vocalisation; ii) inevitably, some of these initial voxels only represent the
line image from their own source, resulting in inconsistent visual impacts on
other viewpoints. To address this, optimisation of a voxel displacement
problem is needed, whereby conflicting voxels are either merged into one or
smoothed with neighbouring voxels as a more holistic visual entity. iii)
Voxels are subjected to further manipulations, often targeting issues more
delicate than inconsistency, including redundancy, complexity, quality, etc..
Much like any rule-based methods for vision problems (SIFT, HOG), these
approaches are advantageous for their full transparency of the playbook but
fall short in generalisation. This is discussed in Sec. 4.3, where existing
approaches, guided by human-informed rules, can create MVWA pieces whose 2D
projections align perfectly with user inputs, but they collapse when faced
with slightly more complex combinations of 2D view images. Reproducing most of
the results shown in Fig. 2 would therefore be a stretch because there is not
yet a rule-based system that can generate arbitrary plausible 2D visual images
from a text string, let alone generating MVWA on top of that.

We face two key challenges: (i) how to represent 3D wire art while ensuring
connectivity (so it does not collapse!), and (ii) how to ensure effective
learning from extremely scarce MVWA training examples. For the former, we
leverage 3D Bézier curves to solve a connectivity (“wiredness”) problem that
cannot be easily achieved in a naive way, such as by chaining control points
(see Fig. 8). Instead, we treat each Bézier curve independently and propose a
loss function to spatially constrain their degree of freedom. At each
iteration, we depict the currently learned wires as a weighted undirected
graph and apply Prim’s algorithm [29] to derive a subset of edges (including
all vertices) corresponding to a minimum spanning tree. The spatial continuity
of wires is thus assured by minimising the distance between each parent and
child vertex. On the latter challenge, we opt for per-instance learning and
base generalisation on knowledge distillation from a powerful generative
visual prior (diffusion models [33] or their variant, _i.e_., ControlNet [45]
in this case). In unison, our system begins with a set of randomly initialised
Bézier curves, which, after 2D projection and vector-to-raster conversion, are
fed into ControlNet to match the user target image and updated via the typical
score distillation sampling (SDS) [28] process.

In summary, our contributions are threefold: (i) empowering everyone to become
a wired 3D (MVWA) artist (even if only half-decent), and scientifically, (ii)
employing Bézier curves and Prim’s algorithm to represent 3D wire art, and
(iii) utilising knowledge distillation from a powerful generative visual prior
through a designed rendering strategy to overcome data scarcity.

Figure 2: MVWA generated via DreamWire. The textual prompts employed
predominantly include “a head of [character]” and “a simple drawing of
[item]”. Notably, all captions for these MVWA have been sourced from ChatGPT
[25]. We prompt it to return three major subjects of interests under a given
topic, _e.g_., three celebrated movie characters of the United States of
America.

##  2 Related work

Vector Graphics. Scalable vector graphics (SVGs), in contrast to images
composed of raster pixels, are defined by extensible markup language (XML)
covering lines, shapes, or curves. Bézier curve is one of the most pronounced
SVG formats, which relies on a set of “control points” to define a smooth line
segment. While there is no denying that computer vision has predominantly
invested in understanding raster images, recent efforts witnessed several
important breakthroughs in the generative modelling of SVGs, mostly for Bézier
curves. BézierSketch [6] first introduced an inverse graphics approach to
sketch stroke embedding that trains an encoder to embed each stroke to its
best fit Bézier curve, and their subsequent work extends this idea to a more
generalised case with variable-degree Bézier control. Another line of works
[19, 7, 34, 43] directly utilise Bézier curves to govern the general-purpose
vector graphic generation process. VectorFusion [15] employs diffusion models
as transferable priors to generate high-quality abstract vector graphics from
text captions. SketchDreamer [30] presents an interactive method for text-
driven vector sketch generation, adeptly incrementing strokes to an initial
vector sketch in accordance with a user-specified text prompt. These works
however only contribute to the application of 2D Bézier curves. We consider
the problem of how to render 3D Bézier curves using a 2D Bézier renderer [19],
which is significantly different from previous work.

Diffusion Prior. There has been a burgeoning interest in denoising diffusion
probabilistic models [11, 39], also known as score-based generative models
[40, 41], thanks to the remarkable generative prowess they have shown.
Consequently, an increasing number of studies [8, 28, 37, 20, 42, 10] emerge
as to how to leverage pretrained diffusion models to act as effective visual
priors for generative supervision. DDPMPnP [8] introduces a partitioning of
diffusion models into a base prior and a conditional constraint, enabling
versatile applications in perceptual tasks like conditional image generation
and segmentation. DreamFusion [28] optimises NeRF parameters using an
efficient, high-fidelity Score Distillation Sampling (SDS) loss, facilitated
by a 2D diffusion image prior to text-to-3D synthesis. Make-A-Video [37]
employs spatial-temporal modules built on 2D text-to-image diffusion models,
realising text-to-video generation without the need for paired samples. We
adopt the idea of applying the diffusion prior to a differentiable image
parameterisation [23] (DIP) as proposed by DreamFusion, with the difference
that we focus on the generation of multi-view wire art.

Multi-View Art. Multi-View Art entails the presentation of multiple
perspectives or views within a singular artwork [24, 17, 3, 2, 35, 14]. The
techniques for achieving varied visual perceptions in an artwork can span a
range of approaches: from altering the viewing distance [24], adjusting the
viewing direction [14, 35], to changing illumination from specific directions
[22, 1, 3]. The underlying factors prompting such phenomena are multifaceted,
including the use of optical materials [44, 27], innovative structural design
[14, 22, 3], or specialised devices [13]. We unprecedentedly introduce
powerful text-to-image generation models to this problem, simplifying and
democratising the art creation process.

##  3 Methodology

###  3.1 Differentiable 3D MVWA rendering

We represent a 3D multi-view wire art $\mathcal{S}$ as a set of individual
wires $\\{s_{1},\cdots,s_{n}\\}$. Each individual wire employs a cubic 3D
Bézier curve, which is rigorously defined by a quartet of 3D control points
$\\{p_{0},p_{1},p_{2},p_{3}\\}$, detailed in Eq. 1:

$\displaystyle
B(t)=(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3},$ (1)

where $t\in[0,1]$. A straightforward approach to render 3D Bézier curves is to
consider a specific plane and calculate the projection of every point along
the curve onto this plane. Given a plane $\pi$ characterised by its normal
vector $N$, the projection of the 3D cubic Bézier curve $B(t)$ onto $\pi$ is
formulated in Eq. 2:

$\displaystyle B^{\prime}(t)=B(t)-[N\cdot(B(t)-q)]N,$ (2)

where $q$ is an arbitrary point on $\pi$. However, prevalent 2D Bézier
rendering techniques, such as the one discussed by [19], as well as 3D point
cloud rendering tools [21, 32, 18], do not support the rendering of such 3D
Bézier curves in Eq. 2. We propose an inquiry: Is it feasible to render 3D
Bézier curves utilising existing 2D Bézier curves renderers? The answer is
YES.

Our objective is to prove that the projection of a 3D Bézier curve onto a
plane, denoted as $B^{\prime}(t)$, is equivalent to the 2D Bézier curve, whose
control points are the projections of the original control points of $B(t)$
onto the same plane, expressed as $B^{\prime\prime}(t)$. Utilising Eq. 2, the
2D Bézier curve $B^{\prime\prime}(t)$ formed by the projection points of
$p_{i}$ on $\pi$ can be expressed as,

$B^{\prime\prime}(t)=(1-t)^{3}p^{\prime}_{0}+3(1-t)^{2}tp^{\prime}_{1}+3(1-t)t^{2}p^{\prime}_{2}+t^{3}p^{\prime}_{3}.$
(3)

The equivalence of $B^{\prime}(t)$ and $B^{\prime\prime}(t)$ can be
systematically demonstrated by applying the principles outlined and the
property of vector addition to expand and transform Eq. 3:

$\displaystyle B^{\prime\prime}(t)$
$\displaystyle=\underbrace{(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}}_{B(t)}-$
(4)
$\displaystyle\\{N\cdot[\underbrace{(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}}_{B(t)}$
$\displaystyle-q]\\}N=B(t)-[N\cdot(B(t)-q)]N=B^{\prime}(t).$

This proof enables us to reframe the challenge of rendering 3D Bézier curves
as essentially a 2D rendering task, anchored in the projection of 3D control
points. Consequently, we are able to directly optimise the 3D wire art
$\mathcal{S}$ using a differentiable 2D Bézier curve renderer, _i.e_., DiffVG
[19].

Figure 3: Schematic overview of DreamWire. Starting from an initial set of
random 3D Bézier curves, we project these curves onto a given 2D plane and
process them into normal raster images. It follows that these images are fed
into a generative diffusion model and optimised towards a visual target. In
addition, we use the MST algorithm to constrain the distance between curves.
Here we present a MVWA sample output under the condition
$\\{c^{X},c^{Y},c^{Z}\\}=\\{$“dog”, “backpack”, “cat”$\\}$.

###  3.2 DreamWire

The overall pipeline of our DreamWire is depicted in Fig. 3. Users just need
to provide three distinct inputs $c=\\{c^{X},c^{Y},c^{Z}\\}$, corresponding to
projections from three mutually orthogonal viewpoints $\\{X,Y,Z\\}$. The
primary objective of our MVWA generation system is to produce a 3D wire art,
$\mathcal{S}$, such that its projections onto each of these viewpoints align
with the user’s specified inputs.

Initially, we initialise a 3D wire art $\mathcal{S}=\\{s_{i}\\}_{i=1}^{n}$,
where the control points of each wire are randomly initialised. We define the
three planes of projection as $\pi^{X},\pi^{Y},\pi^{Z}$, with their
corresponding normal vectors $N^{X},N^{Y},N^{Z}$, which relate to the three
user-provided viewpoints. Utilising Eqs. 3 and 4, we can determine the
projection of $\mathcal{S}$ on plane $\pi^{X}$ as,

$\displaystyle\mathcal{S}^{X}$
$\displaystyle=\\{\hat{s}_{i}^{X}\\}_{i=1}^{n}=\\{\hat{B}_{i}^{X}(t)\\}_{i=1}^{n},$
(5) $\displaystyle\text{where}\quad\hat{B}_{i}^{X}(t)$
$\displaystyle=\sum\nolimits_{j=0}^{3}\binom{3}{j}(1-t)^{3-j}t^{j}\hat{p}^{Xj}_{i},$
$\displaystyle\hat{p}^{Xj}_{i}$
$\displaystyle=p^{j}_{i}-[N^{X}\cdot(p^{j}_{i}-q^{X})]N^{X},$

where $q^{X}$ is any point on plane $\pi^{X}$. We then utilise a
differentiable 2D Bézier curve renderer, denoted as $\mathcal{R}$, to produce
the rasterised projection. These projections are subsequently processed
through the encoder $E_{\phi}$ of a Latent Diffusion Model (LDM) [33],
utilising the Score Distillation Sampling (SDS) loss [28] to estimate
$\mathbf{z}^{X}=E_{\phi}(\mathcal{R}(\mathcal{S}^{X}))$. During each forward
diffusion timestep, we introduce random noise to the latents,
$\mathbf{z}^{X}_{t}=\alpha_{t}\mathbf{z}^{X}+\sigma_{t}\boldsymbol{\epsilon}$,
and apply the teacher model
$\hat{\boldsymbol{\epsilon}}_{\phi}(\mathbf{z}^{X}_{t};t)$, conditioned on
$c^{X}$, for denoising. This process is replicated for $\\{Y,Z\\}$. The
optimisation targets all control points (collectively represented as
$\mathbf{P}$), and is steered by the SDS loss, as expressed in Eq. 6:

$\begin{aligned} \nabla_{\mathbf{P}}\mathcal{L}_{\text{Multi-
SDS}}&=\mathbb{E}_{t,\epsilon}\left[w(t)\Big{(}\hat{\epsilon}_{\phi}(\alpha_{t}\mathbf{z}_{t}^{X}+\sigma_{t}\epsilon;c^{X},t)-\epsilon\Big{)}\frac{\partial\mathbf{z}^{X}}{\partial\mathbf{P}}\right]\\\
&+\mathbb{E}_{t,\epsilon}\left[w(t)\Big{(}\hat{\epsilon}_{\phi}(\alpha_{t}\mathbf{z}_{t}^{Y}+\sigma_{t}\epsilon;c^{Y},t)-\epsilon\Big{)}\frac{\partial\mathbf{z}^{Y}}{\partial\mathbf{P}}\right]\\\
&+\mathbb{E}_{t,\epsilon}\left[w(t)\Big{(}\hat{\epsilon}_{\phi}(\alpha_{t}\mathbf{z}_{t}^{Z}+\sigma_{t}\epsilon;c^{Z},t)-\epsilon\Big{)}\frac{\partial\mathbf{z}^{Z}}{\partial\mathbf{P}}\right].\end{aligned}$

(6)

Here, $w(t)$ represents the weighting function, and $t\in[1,2,\cdots,T]$
denotes the timestep. To afford users greater flexibility in input types, we
adopt the multi-conditional diffusion model approach, as suggested by [30],
utilising a ControlNet [45] to govern the diversity and guide the diffusion
model generation processes. This results in a controllable variant of Eq. 7:

$\nabla_{\mathbf{P}}\mathcal{L}_{\text{CSDS}}=\mathbb{E}_{t,\epsilon}\left[w(t)\left(\hat{\epsilon}_{\phi}(\alpha_{t}\mathbf{z}_{t}+\sigma_{t}\epsilon;c,t,C)-\epsilon\right){\frac{\partial\mathbf{z}}{\partial\mathbf{P}}}\right],$
(7)

where $C$ denotes visual conditions for ControlNet, _e.g_., canny edges, HED
boundaries, user scribbles, human poses, semantic maps, depths, etc. With the
capabilities of ControlNet, users’ input conditions can extend beyond text
captions of visual concepts to include spatial layouts, enabling personalised
customisation.

###  3.3 MVWA to Reality

Technical approach laid out in Sec. 3.2 only allows a digital construct of
MVWA instance within the AR/VR environment. To enable a real tangible MVWA
entity in real life that respects the law of physics however remains highly
challenging. The wires ${s_{1},s_{2},\ldots,s_{n}}$ we acquire so far are
incapable of sustaining stability in suspension; they mandate methodical
interconnections to cultivate a stable and supportive structure. Taking
inspiration from [14], we approach this challenge by framing it as a classic
minimum spanning tree (MST) problem, with the isolated wires and their spatial
relationships represented as a graph. For a set of $n$ wires
$\\{s_{1},s_{2},\ldots,s_{n}\\}$ and $\mathbf{P}$ representing all control
points, we introduce $\ddot{\mathbf{P}}$ to denote the endpoints of all wires.
For any pair of wires $\\{s_{i},s_{j}\\}$, we calculate the Euclidean distance
between their endpoints in four different ways333
$\mathcal{E}_{ij}=min(\parallel p^{0}_{i}-p^{0}_{j}\parallel^{2},\parallel
p^{3}_{i}-p^{0}_{j}\parallel^{2},\parallel
p^{3}_{i}-p^{3}_{j}\parallel^{2},\parallel p^{0}_{i}-p^{3}_{j}\parallel^{2})$,
electing the smallest of these as $\mathcal{E}_{ij}$. Through the assessment
of the Euclidean distances amongst all endpoints, we proceed to construct a
densely interconnected undirected graph $\mathcal{G}$, comprising $n$ vertices
represented as $\\{s_{1},s_{2},\ldots,s_{n}\\}$, with the edges bearing
weights equivalent to $\mathcal{E}_{ij}$.

Figure 4: Effect of the MST regularisation on a set of randomly initialised
Bézier curves.

Our objective is to identify a subset of the edges of $\mathcal{G}$ that binds
all the wires together, forming a cycle-free structure with the minimum
aggregate edge weight. Employing Prim’s Algorithm [29], we derive the minimum
spanning tree, and the associated cost is formulated as follows:

$\mathcal{L}_{\text{MST}}({\ddot{\mathbf{P}}})=\sum
Prim(\mathcal{E}_{ij})\quad i,j\in[1,n].$ (8)

Consequently, our final training objective is articulated as:

$\mathcal{L}=\mathcal{L}_{\text{Multi-
SDS}}(\mathbf{P},c)+\lambda*\mathcal{L}_{\text{MST}}({\ddot{\mathbf{P}}}).$
(9)

Here, $\lambda$ functions as a balancing factor between aesthetic appeal and
structural realism. In Fig. 4, we present a qualitative depiction of the
impact elicited by the MST regularisation, effectively demonstrating how
wires, initially scattered, progressively coalesce into a stable and
integrated structure.

##  4 Experiments

###  4.1 Settings

Implementation. Building upon the methodologies employed in [15] and [30], we
initiate each 3D Bézier curve of MVWA comprising 5 segments, maintaining a
constant width and adopting a uniform black colour. Prior to inputting the 2D
projection of the MVWA into the diffusion model, we employ random affine
augmentations (RandomPerspective and RandomResizedCrop) to refine the
projection’s quality and to reinforce the optimisation process against the
potential adversarial examples. To optimise the MVWA, we employ the Adam
optimiser [16] across 2000 iterations, setting the learning rate to 1. Within
our configuration, we adopt a guidance scale equal to 100. All experiments are
executed on an NVIDIA A100 GPU.

Data preparation. For the visual control setting, to ensure a fair comparison,
the input sets employed are identical to that of the baseline methods [22,
14]. For the text control setting, a selection of 96 daily item categories was
randomly drawn from the QuickDraw dataset [9]. Each category name was then
inserted into a standard template as “a simple drawing of [item]” and these
were subsequently randomised into 32 distinct input sets.

Evaluation metrics. Within the text control setting, we utilise the CLIP [31]
score and R-Precision [26] as metrics to assess the similarity between the
input text condition and 2D rasterised projection of the synthesised MVWA. For
visual control, DINO [5] is employed to quantify the similarity between the 2D
rasterised projection of the generated MVWA and the visual input provided by
the user.

Figure 5: Comparison with existing multi-view wire art synthesis methods. The
user-specified visual controls are highlighted with red lines.  Figure 6:
Additional instances of MVWA generated by our proposed DreamWire with
different random seeds. The text conditions for the MVWA on the left are
defined as $\\{c^{X},c^{Y},c^{Z}\\}=\\{$“a side view of an angel”, “a front
view of an angel” “Christmas bells”$\\}$. Similarly, for the MVWA on the right
are: $\\{c^{X},c^{Y},c^{Z}\\}=\\{$“Hillary”,“Trump”,“Obama”$\\}$. The red
lines indicate the additional connections that need to be added in order to
form all the curves together as a whole. Compared to Our-T, Our-T-$\lambda$
ensures that the red lines are as short as possible while maintaining visual
aesthetics.

###  4.2 Baseline comparison

We compared our approach against two state-of-the-art (SOTA) methods grounded
in traditional graphics algorithms. ShadowArt [22] introduces a novel
geometric optimisation method that automatically finds a consistent shadow
hull by deforming the input images. MVWA [14] starts with reconstructing a
discrete visual hull through intersecting generalised cones formed by back-
projecting the given 2D image to 3D space and integrates the isolated
components into a connected visual hull via a 3D path-finding method. Our-V
and Our-V-$\lambda$ are calibrated to align with the settings of these two
methods, processing three user-specified line drawings alongside corresponding
viewpoints as inputs. Here, $\lambda$ signifies the incorporation of MST
regularisation.

The synthesised 3D wire arts, along with their corresponding 2D projections,
are shown in Fig. 5. We can see that, the voxels yielded by ShadowArt [22] has
a multitude of transformed components, attributable to the markedly
inconsistent nature of the input line drawings, resulting in severely
distorted 2D projections. Conversely, the MVWA [14] aspires to integrate the
isolated components into a connected visual hull via a 3D path-finding method,
inevitably incorporating numerous extraneous lines, thereby compromising the
projected visuals’ fidelity. In contrast, Our-V and Our-V-$\lambda$ are
predicated upon the optimisation of a set of 3D Bézier curves, complemented by
the utilisation of MST loss to emulate the impression of a singular line, a
technique distinctly divergent from the conventional “Voxel Hall Carving”
employed by preceding approaches. Our generated results are slightly inferior
to the results of traditional methods in this setting as our approach cannot
solve the input conflict problem very well. However, given only text as
conditions, our method can generate projections with much higher quality
(refer Fig. 6). In addition, our results possess a more streamlined structural
simplicity within the 3D space compared to traditional methods.

Methods DINO-V2-Base DINO-V2-Giant CLIP Score ShadowArt [22] 79.62 83.82 34.37
MVWA [14] 73.68 78.86 34.81 Ours-V 69.08 72.76 34.55 Ours-V-$\lambda$ 66.99
71.33 32.75 1-4 Ours-T - - 37.21 Ours-T-$\lambda$ - - 36.52

Table 1: DINO similarity (%) between the target sketches and the projection
results and CLIP similarity (%) between the captions and the projection
results generated by different methods.

###  4.3 Main results

As demonstrated in Sec. 4.2, we have previously illustrated the capabilities
of our method under visual control. In this section, we delineate the unique
advantage of our approach over the baselines: our capacity to generate MVWA in
response to textual input or a hybrid of text and visual inputs. This
flexibility significantly diminishes the user’s burden in resolving conflicts
inherent in visual controls.

Qualitative evaluation. In addition to the examples shown in Fig. 1, where we
show the MVWA generated by our method under text and hybrid control, we
further showcase massive cases in Fig. 2 and Fig. 6. For each case, we present
two variations created by Our-T and Our-T-$\lambda$. With MST regularisation,
it becomes apparent that the resulting MVWA bears greater resemblance to
coherent single-line 3D sculptures as opposed to an assemblage of numerous
discrete visual hulls.

Quantitative evaluation. The results are presented in Tab. 4.2. Our method
does not achieve the highest DINO scores on several DINO variants. This is
because our model fits the target sketches by continuously optimising the
parameters of Bézier curves, compared to the search process of traditional
methods, our optimisation method may suffer from underfitting and overfitting
in different regions. Thus, given the layout constraints for various
viewpoints, the traditional methods [22, 14] almost reach the best
performance, and our method is still some distance away from them. However,
given only the text conditions without layout constraints, our method enables
high-quality fit to the target concept in numerous ways, omitting the step of
the artist to elaborate the target projections.

Figure 7: The impact of $\lambda$ on normalised evaluation metrics. Metrics
are normalised to the [0, 1] interval for clarity. The original scale for MST
budget spans [0, 8], for CLIP Score it is [36, 38], and for CLIP R-Prec it
lies between [67, 85].

Ablation on $\lambda$. Fig. 7 illustrates the influence of the $\lambda$
coefficient within $\mathcal{L}_{\text{MST}}$ and CLIP metrics. The increase
of $\lambda$ drives the generated MVWA towards an optimisation that favours a
one-line wire art, leading to a substantial reduction in the wire connectivity
budget. However, this also results in a notable decrease in both the CLIP-
score and R-Precision, suggesting an increased deviation between the user
input and the 2D projection of the synthesised MVWA. Taking into account both
aesthetic appeal and manufacturability, we ultimately set the hyperparameter
$\lambda$ to $50$.

###  4.4 One Line vs. MST Regularisation

In our endeavour to enhance the interconnectedness of generated 3D Bézier
curves thereby more faithfully emulating a single, continuous curve, we have
instituted a novel loss function, denoted as $\mathcal{L}_{\text{MST}}$.
Intuitively, an alternative strategy could entail initialising the 3D wire art
structure as a singular Bézier curve comprised of a substantially high segment
count. Fig. 8 (top) shows the generation result of “a simple drawing of a
bicycle” when the input is a single Bézier curve with 150 segments. For a
clearer presentation, only a 2D Bézier curve is used. It can be noted that a
curve comprising numerous segments may not be able to update their positions
effectively. This problem may lead to substantial segment overlap, thereby
injecting redundancy and detracting from the succinctness of the ultimate
generated form. Therefore, we utilise $\mathcal{L}_{\text{MST}}$ instead of
the one-line setting to ensure that the wire art our model generates is
aesthetically appealing and realistically producible.

Figure 8: Generation of “a simple drawing of a bicycle” starts with a single
curve containing 150 segments (top) and 30 curves containing 5 segments
(bottom) in the same random seed.

##  5 Discussion

It is worth noting that the performance of our proposed method can be
influenced by dataset biases and quality issues, stemming from the use of the
LDM algorithm [4]. Nevertheless, we anticipate that the performance of our
proposed method will be enhanced with the advancements in text-to-image
models. Another aspect worth noting is that [43] emphasises the optimisation
process is susceptible to the initialisation of Bézier curves. Therefore, the
number and width of strokes, where to initialise strokes, and what text prompt
to give each viewpoint may all be issues for artists to consider in future
applications.

##  6 Conclusion

This project is a pioneering venture into the fusion of AI and art, making
strides by enabling AI to easily generate 3D multi-view wire art. It does so
with just brief text prompts or spontaneous scribbles. Beyond its artistic
impact, our work dives into scientific challenges related to abstraction and
3D representation in the generative AI community. The core of our approach
involves refining 3D Bézier curves using diffusion models and a carefully
designed rendering strategy. The ultimate goal is to make this distinct art
form accessible to all, offering a platform for artists, designers, and
enthusiasts to effortlessly bring their imaginative wire sculptures to life.

## References

  * [1] Marc Alexa and Wojciech Matusik.  Reliefs as images.  ACM Transactions on Graphics, 2010.
  * [2] Ilya Baran, Philipp Keller, Derek Bradley, Stelian Coros, Wojciech Jarosz, Derek Nowrouzezahrai, and Markus Gross.  Manufacturing layered attenuators for multiple prescribed shadow images.  Computer Graphics Forum, 2012.
  * [3] Amit Bermano, Ilya Baran, Marc Alexa, and Wojciech Matusk.  Shadowpix: Multiple images from self shadowing.  Computer Graphics Forum, 2012.
  * [4] Abeba Birhane, Vinay Uday Prabhu, and Emmanuel Kahembwe.  Multimodal datasets: misogyny, pornography, and malignant stereotypes.  arXiv:2110.01963, 2021.
  * [5] Mathilde Caron, Hugo Touvron, Ishan Misra, Herv’e J’egou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In ICCV, 2021.
  * [6] Ayan Das, Yongxin Yang, Timothy Hospedales, Tao Xiang, and Yi-Zhe Song.  Béziersketch: A generative model for scalable vector sketches.  In ECCV, 2020.
  * [7] Kevin Frans, Lisa Soros, and Olaf Witkowski.  Clipdraw: Exploring text-to-drawing synthesis through language-image encoders.  In NeurIPS, 2022.
  * [8] Alexandros Graikos, Nikolay Malkin, Nebojsa Jojic, and Dimitris Samaras.  Diffusion models as plug-and-play priors.  In NeurIPS, 2022.
  * [9] David Ha and Douglas Eck.  A Neural Representation of Sketch Drawings.  In ICLR, 2018.
  * [10] Xiao Han, Yukang Cao, Kai Han, Xiatian Zhu, Jiankang Deng, Yi-Zhe Song, Tao Xiang, and Kwan-Yee K. Wong.  Headsculpt: Crafting 3d head avatars with text.  In NeurIPS, 2023.
  * [11] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  In NeurIPS, 2020.
  * [12] Douglas Hofstadter.  Gödel, escher, bach, 1979.  https://en.wikipedia.org/wiki/Gödel,_Escher,_Bach.
  * [13] S Vahab Hosseini, Usman R Alim, A Mahdavi-Amiri, et al.  Portal: design and fabrication of incidence-driven screens.  In SMI, 2020.
  * [14] Kai-Wen Hsiao, Jia-Bin Huang, and Hung-Kuo Chu.  Multi-view wire art.  ACM Transactions on Graphics, 2018.
  * [15] Ajay Jain, Amber Xie, and Pieter Abbeel.  Vectorfusion: Text-to-svg by abstracting pixel-based diffusion models.  In CVPR, 2023.
  * [16] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In ICLR, 2015.
  * [17] Ying-Miao Kuo, Hung-Kuo Chu, Ming-Te Chi, Ruen-Rone Lee, and Tong-Yee Lee.  Generating ambiguous figure-ground images.  IEEE transactions on visualization and computer graphics, 2016.
  * [18] Samuli Laine, Janne Hellsten, Tero Karras, Yeongho Seol, Jaakko Lehtinen, and Timo Aila.  Modular primitives for high-performance differentiable rendering.  ACM Transactions on Graphics, 2020.
  * [19] Tzu-Mao Li, Michal Lukáč, Michaël Gharbi, and Jonathan Ragan-Kelley.  Differentiable vector graphics rasterization for editing and learning.  ACM Transactions on Graphics, 2020.
  * [20] Chen-Hsuan Lin, Jun Gao, Luming Tang, Towaki Takikawa, Xiaohui Zeng, Xun Huang, Karsten Kreis, Sanja Fidler, Ming-Yu Liu, and Tsung-Yi Lin.  Magic3d: High-resolution text-to-3d content creation.  In CVPR, 2023.
  * [21] Shichen Liu, Tianye Li, Weikai Chen, and Hao Li.  Soft rasterizer: A differentiable renderer for image-based 3d reasoning.  In ICCV, 2019.
  * [22] N. J. Mitra and M. Pauly.  Shadow art.  ACM Transactions on Graphics, 2009.
  * [23] Alexander Mordvintsev, Nicola Pezzotti, Ludwig Schubert, and Chris Olah.  Differentiable image parameterizations.  Distill, 2018.
  * [24] Aude Oliva, Antonio Torralba, and Philippe G Schyns.  Hybrid images.  ACM Transactions on Graphics, 2006.
  * [25] OpenAI.  Chatgpt: A large language model, 2023.  https://openai.com/research/chatgpt.
  * [26] Dong Huk Park, Samaneh Azadi, Xihui Liu, Trevor Darrell, and Anna Rohrbach.  Benchmark for compositional text-to-image synthesis.  In NeurIPS, 2021.
  * [27] Maxine Perroni-Scharf and Szymon Rusinkiewicz.  Constructing printable surfaces with view-dependent appearance.  arXiv:2306.07449, 2023.
  * [28] Ben Poole, Ajay Jain, Jonathan T. Barron, and Ben Mildenhall.  Dreamfusion: Text-to-3d using 2d diffusion.  In ICLR, 2023.
  * [29] Robert Clay Prim.  Shortest connection networks and some generalizations.  The Bell System Technical Journal, 1957.
  * [30] Zhiyu Qu, Tao Xiang, and Yi-Zhe Song.  Sketchdreamer: Interactive text-augmented creative sketch ideation.  In BMVC, 2023.
  * [31] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In ICML, 2021.
  * [32] Nikhila Ravi, Jeremy Reizenstein, David Novotny, Taylor Gordon, Wan-Yen Lo, Justin Johnson, and Georgia Gkioxari.  Accelerating 3d deep learning with pytorch3d.  arXiv:2007.08501, 2020.
  * [33] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In CVPR, 2022.
  * [34] Peter Schaldenbrand, Zhixuan Liu, and Jean Oh.  Styleclipdraw: Coupling content and style in text-to-drawing translation.  arXiv:2202.12362, 2022.
  * [35] Guy Sela and Gershon Elber.  Generation of view dependent models using free form deformation.  The Visual Computer, 2007.
  * [36] Zhan Shi, Xu Zhou, Xipeng Qiu, and Xiaodan Zhu.  Improving image captioning with better use of captions.  In ACL, 2020.
  * [37] Uriel Singer, Adam Polyak, Thomas Hayes, Xi Yin, Jie An, Songyang Zhang, Qiyuan Hu, Harry Yang, Oron Ashual, Oran Gafni, et al.  Make-a-video: Text-to-video generation without text-video data.  In ICLR, 2023.
  * [38] Luke Skywalker.  Midjourney, 2023.  https://en.wikipedia.org/wiki/Midjourney.
  * [39] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  In ICLR, 2021.
  * [40] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  In NeurIPS, 2019.
  * [41] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  In ICLR, 2021.
  * [42] Junshu Tang, Tengfei Wang, Bo Zhang, Ting Zhang, Ran Yi, Lizhuang Ma, and Dong Chen.  Make-it-3d: High-fidelity 3d creation from a single image with diffusion prior.  In ICCV, 2023.
  * [43] Yael Vinker, Ehsan Pajouheshgar, Jessica Y. Bo, Roman Christian Bachmann, Amit Haim Bermano, Daniel Cohen-Or, Amir Zamir, and Ariel Shamir.  Clipasso: Semantically-aware object sketching.  ACM Transactions on Graphics, 2022.
  * [44] Jiani Zeng, Honghao Deng, Yunyi Zhu, Michael Wessely, Axel Kilian, and Stefanie Mueller.  Lenticular objects: 3d printed objects with lenticular lens surfaces that can change their appearance depending on the viewpoint.  In UIST, 2021.
  * [45] Lvmin Zhang and Maneesh Agrawala.  Adding conditional control to text-to-image diffusion models.  In ICCV, 2023.

Supplementary Materials for
Wired Perspectives: Multi-View Wire Art Embraces Generative AI

##  Appendix A Differentiable 3D MVWA rendering proof

Any Bézier curve can be represented as the following format:

$B(t)=(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}.$ (10)

Given a plane $\pi$, its normal vector $N$ and a point $q$ in the plane, the
projection of any point $P(t)$ of curve $B(t)$ on plane $\pi$ could be
represented as $P^{\prime}(t)$:

$P^{\prime}(t)=P(t)-(N\cdot(P(t)-q))*N,$ (11)

where $\cdot$ denotes the dot product operation.

Our objective is to prove that the projection of $B(t)$ on the plane $\pi$
($B^{\prime}(t)$) is equal to the curve formed by the projected points of the
control points of that curve
($B^{\prime\prime}(t)=\\{p0^{\prime},p1^{\prime},p2^{\prime},p3^{\prime}\\}$)
on the same plane $\pi$, _i.e_., $B^{\prime}(t)=B^{\prime\prime}(t)$.

Based on Eqs.10 and 11, we can obtain the projection curve $B^{\prime}(t)$ of
$B(t)$ on the plane $\pi$:

$\displaystyle B^{\prime}(t)$
$\displaystyle={\color[rgb]{0.75390625,0.33984375,0.2734375}\definecolor[named]{pgfstrokecolor}{rgb}{0.75390625,0.33984375,0.2734375}[(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}]}$
(12)
$\displaystyle-{\color[rgb]{0.4140625,0.6015625,0.3046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.4140625,0.6015625,0.3046875}\\{N\cdot[(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}-q]\\}*N}.$

We can also obtain the curve $B^{\prime\prime}(t)$ formed by the projected
points of the control points on the plane $\pi$:

$\begin{aligned}
B^{\prime\prime}(t)&=(1-t)^{3}[p_{0}-(N\cdot(p_{0}-q))*N]+3(1-t)^{2}t[p_{1}-(N\cdot(p_{1}-q))*N]+3(1-t)t^{2}[p_{2}-(N\cdot(p_{2}-q))*N]+t^{3}[p_{3}-(N\cdot(p_{3}-q))*N]\\\
&={\color[rgb]{0.75390625,0.33984375,0.2734375}\definecolor[named]{pgfstrokecolor}{rgb}{0.75390625,0.33984375,0.2734375}[(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}]}\\\
&-{\color[rgb]{0.1640625,0.71875,0.79296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.1640625,0.71875,0.79296875}[(1-t)^{3}(N\cdot(p_{0}-q))*N+3(1-t)^{2}t(N\cdot(p_{1}-q))*N}{\color[rgb]{0.1640625,0.71875,0.79296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.1640625,0.71875,0.79296875}\
+3(1-t)t^{2}(N\cdot(p_{2}-q))*N+t^{3}(N\cdot(p_{3}-q))*N]}.\end{aligned}$

(13)

Comparing Eq.12 and 13, we find that the red parts are the same. Therefore, we
only need to show that the blue part in Eq.13 equals to the green part in
Eq.12. Since vector dot product satisfies the distributive over vector
addition properties, _i.e_.,
$\vec{a}\cdot(\vec{b}+\vec{c})=\vec{a}\cdot\vec{b}+\vec{a}\cdot\vec{c}$, we
can deform the blue part of Eq.13 as follows:

$\displaystyle\color[rgb]{0.1640625,0.71875,0.79296875}\definecolor[named]{pgfstrokecolor}{rgb}{0.1640625,0.71875,0.79296875}(1-t)^{3}(N\cdot(p_{0}-q))*N+3(1-t)^{2}t(N\cdot(p_{1}-q))*N+3(1-t)t^{2}(N\cdot(p_{2}-q))*N+t^{3}(N\cdot(p_{3}-q))*N$
(14) $\displaystyle=$
$\displaystyle\\{N\cdot[(1-t)^{3}(p_{0}-q)+3(1-t)^{2}t(p_{1}-q)+3(1-t)t^{2}(p_{2}-q)+t^{3}(p_{3}-q)]\\}*N$
$\displaystyle=$
$\displaystyle\\{N\cdot[(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}-((1-t)^{3}+3(1-t)^{2}t+3(1-t)t^{2}+t^{3})*q)]\\}*N$
$\displaystyle=$
$\displaystyle\color[rgb]{0.4140625,0.6015625,0.3046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.4140625,0.6015625,0.3046875}\\{N\cdot[(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3}-q]\\}*N$

Based on the above proof, we can transform the 3D Bézier curve rendering
problem into a 2D rendering problem based on the projection of 3D control
points. Given a 3D wire and a viewpoint, we can have a raster sketch with the
utilisation of [19] in our 3D to 2D renderer. And more importantly, the whole
process is differentiable.

##  Appendix B Bad case analysis

When we use VectorFusion [15] for 2D sketch generation, the results are
limited by the diffusion prior. In general, given any text prompt, when the
diffusion model generates images well, VectorFusion can also generate great
sketches. However, this is not the case for DreamWire, as there are multi-view
conflicts to consider. We analyse this problem with the following examples.

Fig.9 shows the concepts of “apple”, “banana” and “flower”. However, we can
notice that there is a lot of redundancy present in the sample of “apple”,
_e.g_., some leaves and a logo of “apple” in the centre. Compared to bananas
and flowers, apples have a simpler structure. Therefore, if they are drawn
within the same number of strokes, there are only two scenarios: the apples
are drawn very intricately, or the bananas and flowers are drawn more
abstractly. However, most powerful generative diffusion priors [33, 36] are
trained on images only. This results in them having little abstraction
ability, _i.e_., the ability to outline objects with simple strokes. Based on
this reason, DreamWire is better at making complex sketches, _e.g_.,
“portraits of three people”. This may go against human intuition.

Figure 9: The textual prompts for three viewpoints are “apple”, “banana” and
“flower”, respectively. All prompts possess the following prompt prefix: “a
simple drawing of [text]”.

Fig. 10 shows the concepts of “Walter White”, “Jesse Pinkman” and “Saul
Goodman”. We can notice that there is a lot of redundancy in the sample of
“Walter White”. It’s common knowledge that Walter White is bald while Jesse
Pinkman is not. During our generation process, their heads are positioned at
the same height along the z-axis. Therefore, in order to draw Jesse’s hair,
DreamWire has to add some extra strokes to the sideburns of Walter White. The
potential for conflicting content of different viewpoints is an issue that
users need to consider in future applications.

Figure 10: The textual prompts for three viewpoints are “Walter White”, “Jesse
Pinkman” and “Saul Goodman”, respectively. All prompts possess the following
prompt prefix: “a head of [text]”.