[nc-nd]Kasturi Varadarajan and Xin Xiao Billy Editor, Bill Editors2Conference
title on which this volume is based on111 10.4230/LIPIcs.xxx.yyy.p

# On the Sensitivity of Shape Fitting Problems111This material is based upon
work supported by the National Science Foundation under Grant No. 0915543.

Kasturi Varadarajan  Department of Computer Science
University of Iowa, Iowa City, IA 52242, USA
<EMAIL_ADDRESS>Xin Xiao  Department of Computer Science
University of Iowa, Iowa City, IA 52242, USA
<EMAIL_ADDRESS>
###### Abstract.

In this article, we study shape fitting problems, $\epsilon$-coresets, and
total sensitivity. We focus on the $(j,k)$-projective clustering problems,
including $k$-median/$k$-means, $k$-line clustering, $j$-subspace
approximation, and the integer $(j,k)$-projective clustering problem. We
derive upper bounds of total sensitivities for these problems, and obtain
$\epsilon$-coresets using these upper bounds. Using a dimension-reduction type
argument, we are able to greatly simplify earlier results on total sensitivity
for the $k$-median/$k$-means clustering problems, and obtain positively-
weighted $\epsilon$-coresets for several variants of the $(j,k)$-projective
clustering problem. We also extend an earlier result on $\epsilon$-coresets
for the integer $(j,k)$-projective clustering problem in fixed dimension to
the case of high dimension.

###### Key words and phrases:

Coresets, shape fitting, k-means, subspace approximation

###### 1991 Mathematics Subject Classification:

F.2.2 Analysis of Algorithms and Problem Complexity

##  1\. Introduction

In this article, we study shape fitting problem, coresets, and in particular,
total sensitivity. A shape fitting problem is specified by a triple
$(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, where $\mathbb{R}^{d}$ is the
$d$-dimensional Euclidean space, ${\mathcal{F}}$ is a family of subsets of
$\mathbb{R}^{d}$, and ${\rm
dist}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{+}$ is a continuous
function that we will refer to as a distance function. We also assume that (a)
$\mbox{dist}(p,q)=0$ if and only if $p=q$, and (b)
$\mbox{dist}(p,q)=\mbox{dist}(q,p)$. We refer to each $F\in{\cal F}$ as a
shape, and we require each shape $F$ to be a non-empty, closed, subset of
$\mathbb{R}^{d}$. We define the distance of a point $p\in\mathbb{R}^{d}$ to a
shape $F\in{\cal F}$ to be $\mbox{dist}(p,F)=\min_{q\in F}\mbox{dist}(p,q)$.
An instance of a shape fitting problem is specified by a finite point set
$P\subset\mathbb{R}^{d}$. We slightly abuse notation and use
$\mbox{dist}(P,F)$ to denote $\sum_{p\in P}\mbox{dist}(p,F)$ when $P$ is a set
of points in $\mathbb{R}^{d}$. The goal is to find a shape which best fits
$P$, that is, a shape minimizing $\sum_{p\in P}\mbox{dist}(p,F)$ over all
shapes $F\in{\mathcal{F}}$. This is referred to as the $L_{1}$ fitting
problem, which is the main focus of this paper. In the $L_{\infty}$ fitting
problem, we seek to find a shape $F\in{\mathcal{F}}$ minimizing $\max_{p\in
P}\mbox{dist}(p,F)$.

In this paper, we focus on the $(j,k)$-projective clustering problem. Given
non-negative integers $j$ and $k$, the family of shapes is the set of
$k$-tuples of affine $j$-subspaces (that is, $j$-flats) in $\mathbb{R}^{d}$.
More precisely, each shape is the union of some $k$ $j$-flats. The underlying
distance function is usually the $z^{\rm th}$ power of the Euclidean distance,
for a positive real number $z$. When $j=0$, ${\mathcal{F}}$ is the set of all
$k$-point sets of $\mathbb{R}^{d}$, so the $(0,k)$-projective clustering
problem is the $k$-median clustering problem when the distance function is the
Euclidean distance, and it is the $k$-means clustering problem when the
distance function is the square of the Euclidean distance; when $j=1$, the
family of shapes is the set of $k$-tuples of lines in $\mathbb{R}^{d}$; when
$k=1$, $(j,1)$-projective clustering is the subspace approximation problem,
where the family of shapes is the set of $j$-flats. Other than these
projective clustering problems where $j$ or $k$ is set to specific values,
another variant of the $(j,k)$-projective clustering problem is the integer
$(j,k)$-projective clustering problem, where we assume that the input points
have integer coordinates (but there is no restriction on $j$ and $k$), and the
magnitude of these coordinates is at most $n^{c}$, where $n$ is the number of
input points and $c>0$ is some constant. That is, the points are in a
polynomially large integer grid.

An $\epsilon$-coreset for an instance $P$ of a shape fitting problem is a
weighted set $S$, such that for any shape $F\in{\mathcal{F}}$, the summation
of distances from points in $P$ approximates the weighted summation of the
distances from points in $S$ up to a multiplicative factor of
$(1\pm\epsilon)$. A more precise definition (Definition 2.1) follows later.
Coresets can be considered as a succinct representation of the point set; in
particular, in order to obtain a $(1+\epsilon)$-approximation solution fitting
$P$, it is sufficient to find a $(1+\epsilon)$-approximation solution for the
coreset $S$. One usually seeks a small coreset, whose size $|S|$ is
independent of the cardinality of $P$. Coresets of size $o(n)$ for the
$(j,k)$-projective clustering problem for general $j$ and $k$ are not known to
exist. However, the $k$-median/$k$-means clustering, $k$-line clustering,
$j$-subspace approximation, and integer $(j,k)$-projective clustering problems
admit small coresets.

Langberg and Schulman [10] introduced a general approach to coresets via the
notion of sensitivity of points in a point set, which provides a natural way
to set up a probability distribution $\Pr{\cdot}$ on $P$. Roughly speaking,
the sensitivity of a point with respect to a point set measures the importance
of the point, in terms of fitting shapes in the given family of shapes
${\mathcal{F}}$. Formally, the sensitivity of point $p$ in a point set $P$ is
defined by
$\sigma_{P}(p):=\sup_{F\in{\mathcal{F}}}\mbox{dist}(p,F)/\mbox{dist}(P,F)$.
(In the degenerate case where the denominator in the ratio is $0$, the
numerator is also $0$, and we take the ratio to be $0$; the reader should feel
free to ignore this technicality.) The total sensitivity of a point set $P$ is
defined by $\mathfrak{S}_{P}:=\sum_{p\in P}\sigma_{P}(p)$. The nice property
of quantifying the “importance” of a point in a point set is that for any
$F\in{\mathcal{F}}$, $\mbox{dist}(p,F)/\mbox{dist}(P,F)\leq\sigma_{P}(p)$.
Setting the probability of selecting $p$ to be
$\sigma_{P}(p)/\mathfrak{S}_{P}$, and the weight of $p$ to be
$\mathfrak{S}_{P}/\sigma_{P}(p)$, $\forall p\in P$, one can show that the
variance of the sampling scheme is $O((\mathfrak{S}_{P})^{2})$. When
$\mathfrak{S}_{P}$ is $o(n)$, (for example, a constant or logarithmic in terms
of $n=|P|$), one can obtain an $\epsilon$-coreset by sampling a small number
of points. Langberg and Schulman [10] show that the total sensitivity of any
(arbitrarily large) point set $P\subset\mathbb{R}^{d}$ for
$k$-median/$k$-means clustering problem is a constant, depending only on $k$,
independent of the cardinality of $P$ and the dimension of the Euclidean space
where $P$ and ${\mathcal{F}}$ are from. Using this, they derived a coreset for
these problems with size depending polynomially on $d$ and $k$ and independent
of $n$. Their work can be seen as evolving from earlier work on coresets for
the $k$-median/$k$-means and related problems via other low variance sampling
schemes [3, 4, 7, 5].

Feldman and Langberg [6] relate the notion of an $\epsilon$-coreset with the
well-studied notion of an $\epsilon$-approximation of range spaces. They use a
“functional representation” of points: consider a family of functions
${\mathcal{P}}=\\{f_{p}(\cdot)|p\in P\\}$, where each point $p$ is associated
with a function $f_{p}:X\to\mathbb{R}$. The target here is to pick a small
subset $S\subseteq P$ of points, and assign weights appropriately, so that
$\sum_{p\in S}w_{p}f_{p}(x)$ approximates $\sum_{p\in P}f_{p}(x)$ at every
$x\in X$. When $X$ is ${\mathcal{F}}$ and $f_{p}(F)=\mbox{dist}(p,F)$, this is
just the original $\epsilon$-coreset for $P$. However, $f_{p}(\cdot)$ can be
any other function defined over ${\mathcal{F}}$, for example, $f_{p}(\cdot)$
can be the “residue distance” of $p$, i.e.,
$f_{p}(F)=|\mbox{dist}(p,F)-\mbox{dist}(p^{\prime},F)|$, where $p^{\prime}$ is
the projection of $p$ on the optimum shape $F^{\ast}$ fitting $P$. The
definitions of sensitivities and total sensitivity easily carry over in this
setting: $\sigma_{{\mathcal{P}}}(f_{p})=\sup_{x\in
X}f_{p}(x)/\sum_{f_{q}\in{\mathcal{P}}}f_{q}(x)$ (which coincides with
$\sigma_{P}(p)$ when $f_{p}(\cdot)$ is $\mbox{dist}(p,\cdot)$), and
$\mathfrak{S}_{{\mathcal{P}}}=\sum_{f_{p}\in{\mathcal{P}}}\sigma_{{\mathcal{P}}}(f_{p})$
(which coincides with $\mathfrak{S}_{P}$ similarly). One of the results in [6]
is that an approximating subset $S\subseteq P$ can be computed with the size
$|S|$ upper bounded by the product of two quantities:
$(\mathfrak{S}_{{\mathcal{P}}})^{2}$, and another parameter, the “dimension”
(see Definition 2.3) of a certain range space induced by ${\mathcal{P}}$,
denoted ${\rm dim}\left({\mathcal{P}}\right)$. We remark that ${\rm
dim}\left({\mathcal{P}}\right)$ depends on $d$, which is the dimension of
Euclidean space where $P$ is from, and some other parameters related to $X$;
when $X$ is the family of shapes for the $(j,k)$-projective clustering
problem, ${\rm dim}\left({\mathcal{P}}\right)$ also depends on $j$ and $k$.
This connection allows them to use many results from the well-studied area of
$\epsilon$-approximation of range spaces (such as deterministic construction
of small $\epsilon$-approximation of range spaces), thus constructing smaller
coreset deterministically, and removes some routine analysis in the
traditional way of obtaining coresets via random sampling.

###  1.1. Our Results

In this article, we prove upper bounds of total sensitivities for the
$(j,k)$-projective clustering problems. In particular, we show a careful
analysis of computing total sensitivities for shape fitting problems in high
dimension. Total sensitivity $\mathfrak{S}_{P}$ for a point set
$P\subset\mathbb{R}^{d}$ may depend on $d$: consider the shape fitting problem
where the family of shapes is the set of hyperplanes, and $P$ is a point set
of size $d$ in general position. Then clearly $\sigma_{P}(p)=1$ (since there
always exists a hyperplane containing all $d-1$ points other than $p$), so
$\mathfrak{S}_{P}=d$.

One question that arises naturally is that whether the dependence of the total
sensitivity on the dimension $d$ is essential. To answer this question, we
show that if the distance function is Euclidean distance, or the $z^{\rm th}$
power of Euclidean distance for $z\in[1,\infty)$, then the total sensitivity
function of a shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$ in the high dimensional space $\mathbb{R}^{d}$ is roughly the same as
that of the low-dimensional variant
$(\mathbb{R}^{d^{\prime}},{\mathcal{F}}^{\prime},{\rm dist})$, where
$d^{\prime}$ is the “intrinsic” dimension of the shapes in ${\mathcal{F}}$,
and ${\mathcal{F}}^{\prime}$ consists of shapes contained in the low
dimensional space $\mathbb{R}^{d^{\prime}}$. A reification of this statement
is that the total sensitivity function of the $(j,k)$-projective clustering is
independent of $d$. For the $(j,k)$-projective clustering problems, the shapes
are intrinsically low dimensional: each $k$-tuple of $j$-flats is contained in
a subspace of dimension at most $k(j+1)$. As we will see, the total
sensitivity function for $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, where
${\mathcal{F}}$ is the family of $k$-tuples of $j$-flats in $\mathbb{R}^{d}$,
is of the same magnitude as the total sensitivity function of
$(\mathbb{R}^{f(j,k)},{\mathcal{F}}^{\prime},{\rm dist})$, where $f(j,k)$ is a
function of $j$ and $k$ (which is independent of $d$), and
${\mathcal{F}}^{\prime}$ is the family of $k$-tuples of $j$-flats in
$\mathbb{R}^{f(j,k)}$.

We sketch our approach to upper bound the total sensitivity of the
$(j,k)$-projective clustering. We first make the observation (Theorem 3.2
below) that the total sensitivity of a point set $P$ is upper bounded by a
constant multiple of the total sensitivity of $P^{\prime}={\rm
proj}\left(P,F^{\ast}\right)$, which is the projection of $P$ on the optimum
shape $F^{\ast}$ fitting $P$ in ${\mathcal{F}}$. The computation of total
sensitivity of $P^{\prime}$ is very simple in certain cases; for example, for
$k$-median clustering, $P^{\prime}$ is a multi-set which contains $k$ distinct
points, whose total sensitivity can be directly bounded by $k$. Therefore, we
are able to greatly simplify the proofs in [10]. Another more important use of
this observation is that it allows us to get a dimension-reduction type result
for the $(j,k)$-projective clustering problems: note that although the point
set and the shapes might be in a high dimension space $\mathbb{R}^{d}$, the
projected point set $P^{\prime}$ lies in a subspace of dimension $(j+1)k$
(since each $k$-tuple of $j$-flats is contained in a subspace of dimension at
most $(j+1)k$), which is small under the assumption that both $j$ and $k$ are
constant. Therefore, $\mathfrak{S}_{P}$, which usually depends on $d$ if one
directly computes it in a high dimensional space, depends only on $j$ and $k$,
since $\mathfrak{S}_{P}$ is $O(\mathfrak{S}_{P^{\prime}})$.

Our method for bounding the total sensitivity directly translates into a
template for computing $\epsilon$-coresets:

  1. (1)

Compute $F^{\ast}$, the optimal shape fitting $P$. (It suffices to use an
approximately optimal shape.) Compute $P^{\prime}$, the projection of $P$ onto
$F^{\ast}$.

  2. (2)

Compute a bound on the sensitivity of each point in $P^{\prime}$ with respect
to $P^{\prime}$. Since the ambient dimension is $O(jk)$, we may use a method
that yields bounds on $\mathfrak{S}_{P^{\prime}}$ with dependence on the
ambient dimension. Use Theorem 3.2 to translate this into a bound for
$\sigma_{P}(p)$ for each $p\in P$.

  3. (3)

Sample points from $P$ with probabilities proportional to $\sigma_{P}(p)$ to
obtain a coreset, as described in [10, 6].

We now point out the difference between our usage of total sensitivity in the
construction of coresets and the method in [6]. The construction of coresets
in [6] may also be considered as based on total sensitivity, however in a very
different way:

  1. (1)

First obtain a small weighted point set $S\subseteq P$, such that
$\mbox{dist}(P,F)-\mbox{dist}(P^{\prime},F)$ is approximately the same as
$\mbox{dist}(S,F)-\mbox{dist}(S^{\prime},F)$ ($S^{\prime}$ is ${\rm
proj}\left(S,F^{\ast}\right)$) for every $F\in{\mathcal{F}}$.

  2. (2)

Then compute an $\epsilon$-coreset $Q^{\prime}\subseteq P^{\prime}$ for the
projected point set $P^{\prime}$, that is, $\mbox{dist}(Q^{\prime},F)$
approximates $\mbox{dist}(P^{\prime},F)$ for every $F\in{\mathcal{F}}$. (Since
$P^{\prime}$ is from a low-dimensional subspace, the ambient dimension is
small, and the computation can exploit this.)

Therefore, for each $F\in{\cal F}$,
$\mbox{dist}(P,F)=(\mbox{dist}(P,F)-\mbox{dist}(P^{\prime},F))+\mbox{dist}(P^{\prime},F)\approx(\mbox{dist}(S,F)-\mbox{dist}(S^{\prime},F))+\mbox{dist}(Q^{\prime},F)$.

Thus the weighted set $Q^{\prime}\cup S\cup S^{\prime}$ is a coreset for $P$,
but notice that the points in $S^{\prime}$ have negative weights. In contrast,
the weights of points in the coreset in our construction are positive. The
advantage of getting coresets with positive weights is that in order to get an
approximate solution to the shape fitting problem, we may run algorithms or
heuristics developed for the shape fitting problem on the coreset, such as
[1]. When points have negative weights, on the other hand, some of these
heuristics do not work or need to be modified appropriately.

Another useful feature of the coresets obtained via our results is that the
coreset is a subset of the original point set. When each point stands for a
data item, the coreset inherits a natural interpretation. See [11] for a
discussion of this issue in a broader context.

The sizes of the coresets in this paper are somewhat larger than the size of
coresets in [6]. Roughly speaking, the size of the coreset in [6] is
$f_{1}(d)+f_{2}(j,k)$, where $f_{1}(d)$ (respectively $f_{2}(j,k)$) is a
function depending only on $d$ (respectively $j$ and $k$) for the
$(j,k)$-projective clustering problem, while the coreset size in our paper is
$f_{1}(d)\cdot f_{2}(j,k)$.

Organization of this paper: In this article, we focus on the construction that
establishes small total sensitivity for various shape fitting problems, and
the size of the resulting coreset. For clarity, we omit the description of
algorithms for computing such bounds on sensitivity. Efficient algorithms
result from the construction using a methodology that is now well-understood.
Also because the weights for points in the coreset are nonnegative, the
coreset lend itself to streaming settings, where points arrive one by one as
$p_{1},p_{2},\cdots$ [9][6]. In Section 2, we present necessary definitions
used through this article, and summarize related results from [6] and [12]. In
Section 3, we prove the upper bound of total sensitivity of an instance of a
shape fitting problem in high dimension by its low dimensional projection. In
Sections 4, 5, 6, and 7, we apply the upper bound from Section 3 to
$k$-median/$k$-means, clustering, $k$-line clustering, $j$-subspace
approximation, and the integer $(j,k)$-projective clustering problem,
respectively, to obtain upper bounds for their total sensitivities, and the
size of the resulting $\epsilon$-coresets.

##  2\. Preliminaries

In this section, we formally define some of the concepts studied in this
article, and state crucial results from previous work. We begin by defining an
$\epsilon$-coreset.

######  Definition 2.1 ($\epsilon$-coreset of a shape fitting problem).

Given an instance $P\subset\mathbb{R}^{d}$ of a shape fitting problem
$(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, and $\epsilon\in[0,1]$, an
$\epsilon$-coreset of $P$ is a (weighted) set $S\subseteq P$, together with a
weight function $w:S\to\mathbb{R}^{+}$, such that for any shape $F$ in
${\mathcal{F}}$, it holds that
${\lvert\mbox{dist}(P,F)-\mbox{dist}(S,F)\rvert}\leq\epsilon\cdot\mbox{dist}(P,F)$,
where by definition, $\mbox{dist}(P,F)=\sum_{p\in P}\mbox{dist}(p,F),\mbox{
and }\mbox{dist}(S,F)=\sum_{p\in S}w(p)\mbox{dist}(p,F)$. The size of the
weighted coreset $S$ is defined to be $|S|$.

We note that in the literature, the requirement that the weights be non-
negative, as well as the requirement that the coreset $S$ be a subset of the
original instance $P$, are sometimes relaxed. We include these requirements in
the definition to emphasize that the coresets constructed here do satisfy
them. We now define the sensitivities of points in a shape fitting instance,
and the total sensitivity of the instance.

######  Definition 2.2 (Sensitivity of a shape fitting instance [10]).

Given an instance $P\subset\mathbb{R}^{d}$ of a shape fitting problem
$(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, the sensitivity of a point $p$ in
$P$ is $\sigma_{P}(p):=\inf\\{\beta\geq
0|\mbox{dist}(p,F)\leq\beta\mbox{dist}(P,F),\forall F\in{\mathcal{F}}\\}.$

Note that an equivalent definition is to let
$\sigma_{P}(p)=\sup_{F\in{\mathcal{F}}}\mbox{dist}(p,F)/\mbox{dist}(P,F)$,
with the understanding that when the denominator in the ratio is $0$, the
ratio itself is $0$.

The total sensitivity of the instance $P$, is defined by
$\mathfrak{S}_{P}:=\sum_{p\in P}\sigma_{P}(p)$. The total sensitivity function
of the shape fitting problem is $\mathfrak{S}_{n}:=\sup_{{\lvert
P\rvert}=n}\mathfrak{S}_{P}$.

We now need a somewhat technical definition in order to be able to state an
important earlier result from [6]. On a first reading, the reader is welcome
to skip the detailed definition.

######  Definition 2.3 (The dimension of a shape fitting instance [6]).

Let $P\subset\mathbb{R}^{d}$ be an instance of a shape fitting problem
$(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$. For a weight function
$w:P\to\mathbb{R}^{+}$, consider the set system $(P,{\mathcal{R}})$, where
${\mathcal{R}}$ is a family of subsets of $P$ defined as follows: each element
in ${\mathcal{R}}$ is a set of the form $R_{F,r}$ for some $F\in{\mathcal{F}}$
and $r\geq 0$, and $R_{F,r}=\\{p\in P\ |\ w_{p}\cdot\mbox{dist}(p,F)\leq
r\\}$. That is, $R_{F,r}$ is the set of those points in $P$ whose weighted
distance to the shape $F$ is at most $r$. The dimension of the instance $P$ of
the shape fitting problem, denoted by ${\rm dim}\left(P\right)$, is the
smallest integer $m$, such that for any weight function $w$ and $A\subseteq P$
of size ${\lvert A\rvert}=a\geq 2$, we have: ${\lvert\\{A\cap
R_{F,r}|F\in{\mathcal{F}},r\geq 0\\}\rvert}\leq a^{m}$.

For instance, in the $(j,k)$-projective clustering problem with the underlying
distance function ${\rm dist}$ being the $z^{\rm th}$ power of the Euclidean
distance, the dimension ${\rm dim}\left(P\right)$ of any instance $P$ is
$O(jdk)$, independent of $|P|$ [6]. This is shown by methods similar to the
ones used to bound the VC-dimension of geometric set systems. In fact, this
bound is the only fact that we will need about the dimension of a shape
fitting instance.

The following theorem recalls the connection established in [6] between
coresets and sensitivity via the above notion of dimension.

######  Theorem 2.4 (Connection between total sensitivity and
$\epsilon$-coreset [6]).

Given any $n$-point instance $P\subset\mathbb{R}^{d}$ of a shape fitting
problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, and any
$\epsilon\in(0,1]$, there exists an $\epsilon$-coreset for $P$ of size
$O\left(\left(\frac{\mathfrak{S}_{n}}{\epsilon}\right)^{2}{\rm
dim}\left(P\right)\right)$.

Finally, we will need known bounds on the total sensitivity of
$(j,k)$-projective clustering problem. These earlier bounds involve the
dimension $d$ corresponding to shape fitting problem
$(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$.

######  Theorem 2.5 (Total sensitivity of $(j,k)$-projective clustering
problem in fixed dimension [12]).

We have the following upper bounds of total sensitivities for the
$(j,k)$-projective clustering problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$, where ${\rm dist}$ is the $z$-th power of the Eucldiean distance for
$z\in(0,\infty)$.

  * •

$j=1$ ($k$-line center): $\mathfrak{S}_{n}$ is $O(k^{f(k,d)}\log n)$, where
$f(d,k)$ is a function depending only on $d$ and $k$.

  * •

integer $(j,k)$-projective clustering problem: For any $n$-point instance $P$,
with each coordinate being an integer of magnitude at most $n^{c}$ for any
constant $c>0$, $\mathfrak{S}_{P}$ is $O((\log n)^{f(d,j,k)})$, where
$f(d,j,k)$ is a function depending only on $d$, $j$, and $k$.

##  3\. Bounding the Total Sensitivity via Dimension Reduction

In this section, we show that the total sensitivity of a point set $P$ is of
the same order as that of ${\rm proj}\left(P,F^{\ast}\right)$, which is the
projection of $P$ onto an optimum shape $F^{\ast}$ from ${\mathcal{F}}$
fitting $P$. This result captures the fact that total sensitivity of a shape
fitting problem quantifies the complexity of shapes, in the sense that total
sensitivity depends on the dimension of smallest subspace containing each
shape, regardless of the dimension of the ambient space where $P$ is from.

######  Definition 3.1 (projection of points on a shape).

For a shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$,
define ${\rm proj}:\mathbb{R}^{d}\times{\mathcal{F}}\to\mathbb{R}^{d}$, where
${\rm proj}\left(p,F\right)$ is the projection of $p$ on a shape $F$, that is,
${\rm proj}\left(p,F\right)$ is a point in $F$ which is nearest to $p$, with
ties broken arbitrarily. That is, $\mbox{dist}(p,{\rm
proj}\left(p,F\right))=\min_{q\in F}\mbox{dist}(p,q)$. We abuse the notation
to denote the multi-set $\\{{\rm proj}\left(p,F\right)|p\in P\\}$ by ${\rm
proj}\left(P,F\right)$ for $P\subset\mathbb{R}^{d}$.

We first show that $\mathfrak{S}_{P}$ is $O(\mathfrak{S}_{{\rm
proj}\left(P,F^{\ast}\right)})$, where $F^{\ast}$ is an optimum shape fitting
$P$ from ${\mathcal{F}}$. In particular, this implies that when $F^{\ast}$ is
a low-dimensional object, the total sensitivity of $P\subset\mathbb{R}^{d}$
can be upper bounded by the total sensitivity of a point set contained in a
low dimension subspace.

######  Theorem 3.2 (Dimension reduction, computing the total sensitivity of a
point set in high dimensional space with the projected lower dimensional point
set).

Given an instance $P$ of a shape fitting problem
$(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, let $F^{\ast}$ denote a shape
that minimizes $\mbox{dist}(P,F)$ over all $F\in{\mathcal{F}}$. Let
$p^{\prime}$ denote ${\rm proj}\left(p,F^{\ast}\right)$ and let $P^{\prime}$
denote ${\rm proj}\left(P,F^{\ast}\right)$. Assume that the distance function
satisfies the relaxed triangle inequality:
$\mbox{dist}(p,q)\leq\alpha(\mbox{dist}(p,r)+\mbox{dist}(r,q))$ for any
$p,q,r\in\mathbb{R}^{d}$ for some constant $\alpha\geq 1$. Then

  1. (1)

the following inequality holds: $\mathfrak{S}_{P}\leq
2\alpha^{2}\mathfrak{S}_{P^{\prime}}+\alpha$.

  2. (2)

if $\mbox{dist}(P,F^{\ast})=0$, then
$\sigma_{P}(p)=\sigma_{P^{\prime}}(p^{\prime})$ for each $p\in P$. If
$\mbox{dist}(P,F^{\ast})>0$, then
$\sigma_{P}(p)\leq\left(\alpha\frac{\mbox{dist}(p,p^{\prime})}{\mbox{dist}(P,F^{\ast})}+2\alpha^{2}\sigma_{P^{\prime}}(p^{\prime})\right).$

######  Proof 3.3.

If $\mbox{dist}(P,F^{\ast})=0$, then $P=P^{\prime}$, and clearly both parts of
the theorem hold.

Let us consider the case where $\mbox{dist}(P,F^{\ast})>0$. By definition,

$\displaystyle\sigma_{P}(p)$ $\displaystyle=\inf\\{\beta\geq 0\ |\
\mbox{dist}(p,F)\leq\beta\mbox{dist}(P,F),\forall F\in{\mathcal{F}}\\},$
$\displaystyle\sigma_{P^{\prime}}(p^{\prime})$
$\displaystyle=\inf\\{\beta^{\prime}\geq 0\ |\
\mbox{dist}(p^{\prime},F)\leq\beta^{\prime}\mbox{dist}(P^{\prime},F),\forall
F\in{\mathcal{F}}\\}.$

Let $F$ be an arbitrary shape in ${\mathcal{F}}$. Then we have

$\begin{split}\mbox{dist}(p,F)&\leq\alpha\mbox{dist}(p,p^{\prime})+\alpha\mbox{dist}(p^{\prime},F)\\\
&\leq\alpha\mbox{dist}(p,p^{\prime})+\alpha\sigma_{P^{\prime}}(p^{\prime})\mbox{dist}(P^{\prime},F)\\\
&\leq\alpha\mbox{dist}(p,p^{\prime})+2\alpha^{2}\sigma_{P^{\prime}}(p^{\prime})\mbox{dist}(P,F)\\\
&=\alpha\frac{\mbox{dist}(p,p^{\prime})}{\mbox{dist}(P,F)}\cdot\mbox{dist}(P,F)+2\alpha^{2}\sigma_{P^{\prime}}(p^{\prime})\mbox{dist}(P,F)\\\
&\leq\alpha\frac{\mbox{dist}(p,p^{\prime})}{\mbox{dist}(P,F^{\ast})}\cdot\mbox{dist}(P,F)+2\alpha^{2}\sigma_{P^{\prime}}(p^{\prime})\mbox{dist}(P,F)\\\
&=\left(\alpha\frac{\mbox{dist}(p,p^{\prime})}{\mbox{dist}(P,F^{\ast})}+2\alpha^{2}\sigma_{P^{\prime}}(p^{\prime})\right)\mbox{dist}(P,F).\end{split}$

The first inequality follows from the relaxed triangle inequality, the second
inequality follows from the definition of sensitivity of $p^{\prime}$ in
$P^{\prime}$, and third inequality follows from the fact that
$\mbox{dist}(P^{\prime},F)=\sum_{p^{\prime}\in
P^{\prime}}\mbox{dist}(p^{\prime},F)\leq\sum_{p\in
P}\alpha\left(\mbox{dist}(p,F)+\mbox{dist}(p,p^{\prime})\right)=\alpha(\mbox{dist}(P,F)+\mbox{dist}(P,F^{\ast}))\leq
2\alpha\mbox{dist}(P,F),$ since $\mbox{dist}(P,F^{\ast})\leq\mbox{dist}(P,F)$.

Thus the second part of the theorem holds. Now,

$\displaystyle\mathfrak{S}_{P}$ $\displaystyle=$ $\displaystyle\sum_{p\in
P}\sigma_{P}(p)$ $\displaystyle\leq$ $\displaystyle\sum_{p\in
P}\left(\alpha\frac{\mbox{dist}(p,p^{\prime})}{\mbox{dist}(P,F^{\ast})}+2\alpha^{2}\sigma_{P^{\prime}}(p^{\prime})\right)$
$\displaystyle=$ $\displaystyle\alpha+2\alpha^{2}\mathfrak{S}_{P^{\prime}}.$

We make a remark regarding the value of $\alpha$ in Theorem 3.2 when the
distance function is $z^{\rm th}$ power of Euclidean distance. It is used in
Sections 4, 5, 6, and 7 when we derive upper bounds of total sensitivities for
various shape fitting problems.

######  Remark 3.4 (Value of $\alpha$ when
$\mbox{dist}(\cdot,\cdot)=(\|\,\cdot\,\|_{2})^{z}$).

Let $z\in(0,\infty)$. Suppose $\mbox{dist}(p,q)=(\|\,p-q\,\|_{2})^{z}$. When
$z\in(0,1)$, the weak triangle inequality holds with $\alpha=1$; when $z\geq
1$, the weak triangle inequality holds with $\alpha=2^{z-1}$. For a proof,
see, for example, [8].

Theorem 3.2 bounds the total sensitivity of an instance $P$ of a shape fitting
problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$ in terms of the total
sensitivity of $P^{\prime}$. Suppose that there is an $m_{2}\ll d$ so that
each shape $F\in{\mathcal{F}}$ is in some subspace of dimension $m_{2}$. In
the $(j,k)$-projective clustering problem, for example, $m_{2}=k(j+1)$. Then
note that $P^{\prime}$ is contained in a subspace of dimension $m_{2}$.
Furthermore, when ${\rm dist}$ is the $z^{\rm th}$ power of the Euclidean
distance, it turns out that for many shape fitting problems the sensitivity of
$P^{\prime}$ can be bounded as if the shape fitting problem was housed in
$\mathbb{R}^{2m_{2}}$ instead of $\mathbb{R}^{d}$. To see why this is the case
for the $(j,k)$-projective clustering problem, fix an arbitrary subspace $G$
of dimension $\min\\{d,2m_{2}\\}$ that contains $P^{\prime}$. Then for for any
$F\in{\mathcal{F}}$, there is an $F^{\prime}\in{\mathcal{F}}$ such that (a)
$F^{\prime}$ is contained in $G$, and (b)
$\mbox{dist}(p^{\prime},F^{\prime})=\mbox{dist}(p^{\prime},F)$ for all
$p^{\prime}\in P^{\prime}$.

The following theorem summarizes this phenomenon. For simplicity, it is stated
for the $(j,k)$-projective clustering problem, even though the phenomenon
itself is somewhat more general.

######  Theorem 3.5 (Sensitivity of a lower dimensional point set in a high
dimensional space).

Let $P^{\prime}$ be an $n$-point instance of the $(j,k)$-projective clustering
problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$, where ${\rm dist}$ is the
$z^{\rm th}$ power of the Euclidean distance, for some $z\in(0,\infty)$.
Assume that $P^{\prime}$ is contained in a subspace of dimension $m_{1}$.
(Note that for each shape $F\in{\mathcal{F}}$, there is a subspace of
dimension $m_{2}=k(j+1)$ containing it.) Let $G$ be any subspace of dimension
$m=\min\\{m_{1}+m_{2},d\\}$ containing $P^{\prime}$; fix an orthonormal basis
for $G$, and for each $p^{\prime}\in P^{\prime}$, let
$p^{\prime\prime}\in\mathbb{R}^{m}$ be the coordinates of $p^{\prime}$ in
terms of this basis. Let $P^{\prime\prime}=\\{p^{\prime\prime}\ \mid\
p^{\prime}\in P^{\prime}\\}$, and view $P^{\prime\prime}$ as an instance of
the $(j,k)$-projective clustering problem
$(\mathbb{R}^{m},{\mathcal{F}}^{\prime},{\rm dist})$, where
${\mathcal{F}}^{\prime}$ is the set of all $k$-tuples of $j$-subspaces in
$\mathbb{R}^{m}$, and ${\rm dist}$ is the $z^{\rm th}$ power of the Eucldiean
distance. Then,
$\sigma_{P^{\prime}}(p^{\prime})=\sigma_{P^{\prime\prime}}(p^{\prime\prime})$
for each $p^{\prime}\in P^{\prime}$, and
$\mathfrak{S}_{P^{\prime}}=\mathfrak{S}_{P^{\prime\prime}}$.

##  4\. $k$-median/$k$-means Clustering Problem

In this section, we derive upper bounds for the total sensitivity function for
the $k$-median/$k$-means problems, and its generalizations, where the distance
function is $z^{\rm th}$ power of Euclidean distance, using the approach in
Section 4. These bounds are similar to the ones derived by Langberg and
Schulman [10], but the proof is much simplified. For the rest of the article,
${\rm dist}$ is assumed to be the $z^{\rm th}$ power of the Euclidean
distance.

######  Theorem 4.1 (Total sensitivity of $(0,k)$-projective clustering).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$, where ${\mathcal{F}}$ is the set of all $k$-point subsets of
$\mathbb{R}^{d}$. We have the following upper bound on the total sensitivity:

$\displaystyle\mathfrak{S}_{n}$ $\displaystyle\leq 2^{2z-1}k+2^{z-1},$
$\displaystyle z\geq 1,$ $\displaystyle\mathfrak{S}_{n}$ $\displaystyle\leq
2k+1,$ $\displaystyle z\in(0,1).$

In particular, the total sensitivity of the $k$-median problem (which
corresponds to the case when $z=1$) is at most $2k+1$, and the total
sensitivity of the $k$-means problem (which corresponds to the case when
$z=2$) is $8k+2$.

######  Proof 4.2.

Let $P$ be an arbitrary $n$-point set. Apply Theorem 3.2, and note that ${\rm
proj}\left(P,C^{\ast}\right)$, where $C^{\ast}$ is an optimum set of $k$
centers, contains at most $k$ distinct points. Assume that
$C^{\ast}=\\{c_{1}^{\ast},c_{2}^{\ast},\cdots,c_{k}^{\ast}\\}$. Let $P_{i}$ be
the set of points in $P$ whose projection is $c_{i}^{\ast}$, that is,
$P_{i}=\\{p\in P|{\rm proj}\left(p,C^{\ast}\right)=c_{i}^{\ast}\\}$. It is
easy to see that the summation of sensitivities of the ${\lvert P_{i}\rvert}$
copies of $c_{i}^{\ast}$ is at most 1: for any $k$-point set $C$ in
$\mathbb{R}^{d}$, ${\lvert
P_{i}\rvert}\cdot\frac{\mbox{dist}(c_{i}^{\ast},C)}{\mbox{dist}(C^{\ast},C)}=\frac{{\lvert
P_{i}\rvert}\mbox{dist}(c_{i}^{\ast},C)}{\sum_{j=1}^{k}{\lvert
P_{j}\rvert}\mbox{dist}(c_{j}^{\ast},C)}\leq 1$.

Therefore, the total sensitivity of ${\rm proj}\left(P,C^{\ast}\right)$ is at
most $k$. Substituting $\alpha$ from the remark after Theorem 3.2, we get the
above result.

######  Theorem 4.3 ($\epsilon$-coreset for $(0,k)$-projective clustering).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$, where ${\mathcal{F}}$ is the set of all $k$-point subsets of
$\mathbb{R}^{d}$. For any $n$-point instance $P$, there is an
$\epsilon$-coreset of size $O(k^{3}d\epsilon^{-2})$.

######  Proof 4.4.

Observe that the ${\rm dim}\left(P\right)$ is $O(kd)$. Using Theorem 2.4, and
Theorem 4.1, we obtain the above result.

##  5\. $k$-line Clustering Problem

In this section, we derive upper bounds on the total sensitivity function for
the $k$-line clustering problem, that is, the $(1,k)$-projective clustering
problem.

######  Theorem 5.1 (Total sensitivity for $k$-line clustering problem).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$, where ${\mathcal{F}}$ is the set of $k$-tuple of lines. The total
sensitivity function, $\mathfrak{S}_{n}$, is $O(k^{f(k)}\log n)$, where $f(k)$
is a function the depends only on $k$.

######  Proof 5.2.

Let $P$ be an arbitrary $n$-point set. Let $K^{\ast}$ denote an optimum set of
$k$ lines fitting $P$. Using Theorems 3.2 and 3.5, it suffices to bound the
sensitivity of an $n$-point instance of a $k$-line clustering problem housed
in $\mathbb{R}^{4k}$. By Theorem 2.5, the total sensitivity of this latter
shape fitting problem is $O(k^{f(k)}\log n)$, where $f(k)$ is a function
depending only on $k$. Therefore, $\mathfrak{S}_{n}$ is $O(k^{f(k)}\log n)$.

(Alternatively, one could use a recent result in [8]. Let $P^{\prime}$ denote
the projection of $P$ into $K^{\ast}$. Since $K^{\ast}$ is a union of $k$
lines, we can upper bound the sensitivity of $P^{\prime}$ by $k$ times the
sensitivity of an $n$-point set that lies on a single line. The sensitivity of
an $n$-point set that lies on a single line can be upper bounded by the
sensitivity of an $n$-point set for the weighted $(0,k)$-projective clustering
problem, for which the sensitivity bound is $O(k^{f(k)}\log n)$ as shown in
[8].)

Notice that for $k$-line clustering problem, the bound on the total
sensitivity depends logarithmically on $n$. We give below a construction of a
point set that shows that this is necessary, even for $d=2$.

######  Theorem 5.3 (The upper bound of total sensitivity for $k$-line
clustering problem is tight).

For every $n\geq 2$, there exists an $n$-point instance of the $k$-line
clustering problem $(\mathbb{R}^{2},{\mathcal{F}},{\rm dist})$, where ${\rm
dist}$ is the Euclidean distance, such that the total sensitivity of $P$ is
$\Omega(\log n)$.

######  Proof 5.4.

We construct a point set $P$ of size $n$, together with $n$ shapes
$F_{i}\in{\mathcal{F}}$, $i=1,\cdots,n$, such that
$\sum_{i=1}^{n}\mbox{dist}(p_{i},F_{i})/\mbox{dist}(P,F_{i})$ is $\Omega(\log
n)$. Note that this implies that $\mathfrak{S}_{P}$ is at least $\Omega(\log
n)$. Let $P$ be the following point set in $\mathbb{R}^{2}$:
$p_{i}=(1/2^{i-1},0)$, for $i=1,\cdots,n$. Let $F_{i}$ be a pair of lines: one
vertical line and one horizontal line, where the vertical line is the
$y$-axis, and the horizontal line is $\\{(x,1/2^{i})|x\in\mathbb{R}\\}$.

Consider the point $p_{i}$, where $i=1,\cdots,n$. We show that
$\mbox{dist}(p_{i},F_{i})/\mbox{dist}(P,F_{i})$ is at least $1/(2+i)$, for
$i=1,\cdots,n$. For $j\leq i$, note that $\mbox{dist}(p_{j},F_{i})=1/2^{i}$:
since the distance from $p_{j}$ to the horizontal line in $F_{i}$ is $1/2^{i}$
and the distance to the vertical line is $1/2^{j-1}$,
$\mbox{dist}(p_{j},F_{i})=\min\\{1/2^{j-1},1/2^{i}\\}=1/2^{i}$. For $i+1\leq
j\leq n$, on the other hand, $\mbox{dist}(p_{j},F_{i})=1/2^{j-1}$. Therefore,
$\sum_{j=i+1}^{n}\mbox{dist}(p_{j},F_{i})=\sum_{j=i+1}^{n}1/2^{j-1}=(1/2^{i-1})\cdot(1-(1/2)^{n-i})$.
Thus, we have

$\sigma_{P}(p_{i})=\sup_{F\in{\mathcal{F}}}\frac{\mbox{dist}(p_{i},F)}{\mbox{dist}(P,F)}\geq\frac{\mbox{dist}(p_{i},F_{i})}{\mbox{dist}(P,F_{i})}=\frac{1/2^{i}}{(1/2^{i-1}-1/2^{n-1})+i\cdot(1/2^{i})}>\frac{1}{2+i}$

Therefore,
$\mathfrak{S}_{P}\geq\sum_{i=1}^{n}\sigma_{P}(p_{i})>\sum_{i=1}^{n}\frac{1}{2+i}$,
which is $\Omega(\log n)$.

######  Theorem 5.5 ($\epsilon$-coreset for $k$-line clustering problem).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$, where ${\mathcal{F}}$ is the set of all $k$-tuples of lines in
$\mathbb{R}^{d}$. For any $n$-point instance $P$, there is an
$\epsilon$-coreset with size $O(k^{f(k)}d(\log n)^{2}/\epsilon^{2})$.

######  Proof 5.6.

This result follows from Theorem 5.1, Theorem 2.4, and the fact that ${\rm
dim}\left(P\right)$ in this case is $O(kd)$.

##  6\. Subspace approximation

In this section, we derive upper bounds on the sensitivity of the subspace
approximation problem, that is, the $(j,1)$-projective clustering problem. For
the applications of Theorems 3.2 and 3.5 in the other sections, we use
existing bounds on the sensitivity that have a dependence on the dimension
$d$. For the subspace approximation problem, however, we derive here the
dimension-dependent bounds on sensitivity by generalizing an argument from
[10] for the case $j=d-1$ and $z=2$. This derivation is somewhat technical.
With these bounds in hand, the derivation of the dimension-independent bounds
is readily accomplished in a manner similar to the other sections.

distance. Although the size of the $\epsilon$-coreset obtained in this way is
exponential in $j$, which is larger than the size of the coreset in
[6][feldmanarvix] and Theorem LABEL: in this section, it is still a constant
(as $j$ is considered as a constant) and in particular, independent of the
cardinality of the input point set. It can be considered as an simple and
straight-forward way to see why small $\epsilon$-coresets exist for
$j$-subspace approximation problems.

###  6.1. Dimension-dependent bounds on Sensitivity

We first recall the notion of an _$(\alpha,\beta,z)$ -conditioned basis_ from
[5], and state one of its properties (Lemma 6.2). We will use standard matrix
terminilogy: $m_{ij}$ denotes the entry in the $i$-th row and $j$-th column of
$M$, and $M_{i\cdot}$ is the $i$-th row of $M$.

######  Definition 6.1.

Let $M$ be an $n\times m$ matrix of rank $\rho$. Let $z\in[1,\infty)$, and
$\alpha,\beta\geq 1$. An $n\times\rho$ matrix $A$ is an
$(\alpha,\beta,z)$-conditioned basis for $M$ if the column vectors of $A$ span
the column space of $M$, and additionally $A$ satisfies that: (1)
$\sum_{i,j}{\lvert a_{ij}\rvert}^{z}\leq\alpha^{z}$, (2) for all
$u\in\mathbb{R}^{\rho}$, $\|\,u\,\|_{z^{\prime}}\leq\beta\|\,Au\,\|_{z}$,
where $\|\,\cdot\,\|_{z^{\prime}}$ is the dual norm for $\|\,\cdot\,\|_{z}$
(i.e. $1/z+1/z^{\prime}=1$).

######  Lemma 6.2.

Let $M$ be an $n\times m$ matrix of rank $\rho$. Let $z\in[1,\infty)$. Let $A$
be an $(\alpha,\beta,z)$-conditioned basis for $M$. For every vector
$u\in\mathbb{R}^{m}$, the following inequality holds: ${\lvert
M_{i\cdot}u\rvert}^{z}\leq\left(\|\,A_{i\cdot}\,\|_{z}^{z}\cdot\beta^{z}\right)\|\,Mu\,\|_{z}^{z}$.

######  Proof 6.3.

We have $M=A\tau$ for some $\rho\times m$ matrix $\tau$. Then,

${\lvert M_{i\cdot}u\rvert}^{z}={\lvert A_{i\cdot}\tau
u\rvert}^{z}\leq\|\,A_{i\cdot}\,\|_{z}^{z}\cdot\|\,\tau
u\,\|_{z^{\prime}}^{z}\leq\|\,A_{i\cdot}\,\|_{z}^{z}\cdot\beta^{z}\|\,A\tau
u\,\|_{z}^{z}=\|\,A_{i\cdot}\,\|_{z}^{z}\cdot\beta^{z}\|\,Mu\,\|_{z}^{z}.$

The second step is Holder’s inequality, and the third uses the fact that $A$
is $(\alpha,\beta,z)$-conditioned.

Using Lemma 6.2, we derive an upper bound on the total sensitivity when each
shape is a hyperplane.

######  Lemma 6.4 (total sensitivity for fitting a hyperplane).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$
where ${\mathcal{F}}$ is the set of all $(d-1)$-flats, that is, hyperplanes.
The total sensitivity of any $n$-point set is $O(d^{1+z/2})$ for $1\leq z<2$,
$O(d)$ for $z=2$, and $O(d^{z})$ for $z>2$.

######  Proof 6.5.

We can parameterize a hyperplane with a vector in $\mathbb{R}^{d+1}$,
$u=\begin{bmatrix}u_{1}&\cdots&u_{d+1}\end{bmatrix}^{T}$: the hyperplane
determined by $u$ is
$h_{u}=\\{x\in\mathbb{R}^{d}|\sum_{i=1}^{d}u_{i}x_{i}+u_{d+1}=0\\}$, where
$x_{i}$ denotes the $i^{\rm th}$ entry of the vector $x$. Without loss of
generality, we may assume that $\sum_{i=1}^{d}u_{i}^{2}=1$. The Euclidean
distance to $h_{u}$ from a point $q\in\mathbb{R}^{d}$ is
$\mbox{dist}(q,h_{u})={\lvert\sum_{i=1}^{d}u_{i}q_{i}+u_{d+1}\rvert}/\sqrt{\sum_{i=1}^{d}u_{i}^{2}}={\lvert\sum_{i=1}^{d}u_{i}q_{i}+u_{d+1}\rvert}.$
(the second equality follows from the assumption that
$\sum_{i=1}^{d}u_{i}^{2}=1$.)

Let $P=\\{p_{1},p_{2},\ldots,p_{n}\\}\subseteq\mathbb{R}^{d}$ be any set of
$n$ points. Let $\tilde{p_{i}}$ denote the row vector
$\begin{bmatrix}p_{i}^{T}&1\end{bmatrix}$, and let $M$ be the $n\times(d+1)$
matrix whose $i^{\rm th}$ row is $\tilde{p_{i}}$. Then,
$\mbox{dist}(p_{i},h_{u})={\lvert M_{i\cdot}u\rvert}^{z}$, and
$\mbox{dist}(P,h_{u})=\sum_{i=1}^{n}{\lvert
M_{i\cdot}u\rvert}^{z}=\|\,Mu\,\|_{z}^{z}$. Then using Lemma 6.2, we have
$\sigma_{P}(p_{i})=\sup_{u}\frac{{\lvert
M_{i\cdot}u\rvert}^{z}}{\|\,Mu\,\|_{z}^{z}}\leq\|\,A_{i\cdot}\,\|_{z}^{z}\cdot\beta^{z}$,
where $A$ is an $(\alpha,\beta,z)$-conditioned basis for $M$. Thus,

$\mathfrak{S}_{P}=\sum_{i=1}^{n}\sigma_{P}(p_{i})\leq\beta^{z}\sum_{i=1}^{n}\|\,A_{i\cdot}\,\|_{z}^{z}=\beta^{z}\sum_{i,j}{\lvert
a_{ij}\rvert}^{z}=(\alpha\beta)^{z}.$

For $1\leq z<2$, $M$ has $((d+1)^{1/z+1/2},1,z)$-conditioned basis; for $z=2$,
$M$ has $((d+1)^{1/2},1,z)$-conditioned basis; for $z>2$, $M$ has
$((d+1)^{1/z+1/2},(d+1)^{1/z^{\prime}-1/2},z)$-conditioned basis [5]. Thus the
total sensitivity for the three cases are $(d+1)^{1+z/2}$, $d+1$, and
$(d+1)^{z}$, respectively.

It is now easy to derive dimension-dependent bounds on the sensitivity when
each shape is a $j$-subspace.

######  Corollary 6.6 (Total sensitivity for fitting a $j$-subspace).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$
where ${\mathcal{F}}$ is the set of all $j$-flats. The total sensitivity of
any $n$-point set is $O(d^{1+z/2})$ for $1\leq z<2$, $O(d)$ for $z=2$, and
$O(d^{z})$ for $z>2$.

######  Proof 6.7.

Denote by ${\mathcal{F}}^{\prime}$ the set of hyperplanes in $\mathbb{R}^{d}$.
Let $P\subseteq\mathbb{R}^{d}$ be an arbitrary $n$-point set. We first show
that $\sigma_{P,{\mathcal{F}}}(p)\leq\sigma_{P,{\mathcal{F}}^{\prime}}(p)$,
where the additional subscript is being used to indicate which shape fitting
problem we are talking about (hyperplanes or $j$-flats). Let $p$ be an
arbitrary point in $P$. Let $F_{p}\in{\mathcal{F}}$ denote the $j$-subspace
such that
$\sigma_{P,{\mathcal{F}}}(p)=\mbox{dist}(p,F_{p})/\mbox{dist}(P,F_{p})$. Let
${\rm proj}\left(p,F_{p}\right)$ denote the projection of $p$ on $F_{p}$.
Consider the hyperplane $F^{\prime}$ containing $F_{p}$ and orthogonal to the
vector $p-{\rm proj}\left(p,F_{p}\right)$. We have
$\mbox{dist}(p,F^{\prime})=\mbox{dist}(p,F_{p})$, whereas
$\mbox{dist}(q,F^{\prime})\leq\mbox{dist}(q,F_{p})$ for each $q\in P$.
Therefore,
$\sigma_{P,{\mathcal{F}}^{\prime}}(p)\geq\mbox{dist}(p,F^{\prime})/\mbox{dist}(P,F^{\prime})\geq\mbox{dist}(p,F_{p})/\mbox{dist}(P,F_{p})=\sigma_{P,{\mathcal{F}}}(p).$
It follows that
$\mathfrak{S}_{P,{\mathcal{F}}}\leq\mathfrak{S}_{P,{\mathcal{F}}^{\prime}}$.
The statement in the corollary now follows from Lemma 6.4.

###  6.2. Dimension-independent Bounds on the Sensitivity

We now derive dimension-independent upper bounds for the total sensitivity for
the $j$-subspace fitting problem.

######  Theorem 6.8 (Total sensitivity for $j$-subspace fitting problem).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$
where ${\mathcal{F}}$ is the set of all $j$-flats. The total sensitivity of
any $n$-point set is $O(j^{1+z/2})$ for $1\leq z<2$, $O(j)$ for $z=2$, and
$O(j^{z})$ for $z>2$.

######  Proof 6.9.

Use Theorem 3.2, note that the projected point set $P^{\prime}$ is contained
in a $j$-subspace. Further, each shape is a $j$-subspace. So, applying Theorem
3.5 and Corollary 6.6, the total sensitivity is $O(j^{2+z/2})$ or $z\in[1,2)$,
$O(j)$ for $z=2$ and $O(j^{z})$ for $z>2$.

Using Theorem 6.8 and the fact that ${\rm dim}\left(P\right)$ for the
$j$-subspace fitting problem is $O(jd)$, we obtain small $\epsilon$-coresets:

######  Theorem 6.10 ($\epsilon$-coreset for $j$-subspace fitting problem).

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm dist})$
where ${\mathcal{F}}$ is the set of all $j$-flats. For any $n$-point set,
there exists an $\epsilon$-coreset whose size is $O(j^{3+z}d\epsilon^{-2})$
for $z\in[1,2)$, $O(j^{3}d\epsilon^{-2})$ for $z=2$ and
$O(j^{2z+1}d\epsilon^{-2})$ for $z\geq 2$.

######  Proof 6.11.

The result follows from Theorem 6.8, and Theorem 2.4.

We note that for the case $j=d-1$ and $z=2$, a linear algebraic result from
[2] yields a coreset whose size is an improved $O(d\epsilon^{-2})$.

##  7\. The $(j,k)$ integer projective clustering

######  Theorem 7.1.

Consider the shape fitting problem $(\mathbb{R}^{d},{\mathcal{F}},{\rm
dist})$, where ${\mathcal{F}}$ is the set of $k$-tuples of $j$-flats. Let
$P\subset\mathbb{R}^{d}$ be any $n$-point instance with integer coordinates,
the magnitude of each coordinate being at most $n^{c}$, for some constant $c$.
The total sensitivity $\mathfrak{S}_{P}$ of $P$ is $O((\log n)^{f(k,j)})$,
where $f(k,j)$ is a function of only $k$ and $j$. There exists an
$\epsilon$-coreset for $P$ of size $O((\log n)^{2f(k,j)}kjd\epsilon^{-2})$.

######  Proof 7.2.

Observe that the projected point set $P^{\prime}={\rm
proj}\left(P,\\{J_{1}^{\ast},\cdots,J_{k}^{\ast}\\}\right)$, where
$\\{J_{1}^{\ast},\cdots,J_{k}^{\ast}\\}$ is an optimum $k$-tuple of $j$-flats
fitting $P$, is contained in a subspace of dimension $O(jk)$. Using Theorem
2.5, Theorem 3.5, and Theorem 3.2, the total sensitivity $\mathfrak{S}_{P}$ is
upper bouned by $O((\log n)^{f(k,j)})$, where $f(k,j)$ is a function of $k$
and $j$. (A technical complication is that the coordinates of $P^{\prime}$, in
the appropriate orthonormal basis, may not be integers. This can be addressed
by rounding them to integers, at the expense of increasing the constant $c$. A
similar procedure is adopted in [12], and we omit the details here.)

Using Theorem 2.4 and the fact that ${\rm dim}\left(P\right)$ is $O(djk)$, we
obtain the bound on the coreset.

##  8\. Acknowledgements.

We thank the anonymous reviewers and Dan Feldman for their insightful
feedback.

## References

  * [1] Pankaj K. Agarwal and Nabil H. Mustafa.  $k$-Means projective clustering.  In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’04, pages 155–165, New York, NY, USA, 2004. ACM.
  * [2] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava.  Twice-Ramanujan sparsifiers.  In STOC, pages 255–262, 2009.
  * [3] Ke Chen.  On coresets for $k$-median and $k$-means clustering in metric and euclidean spaces and their applications.  SIAM J. Comput., 39(3):923–947, 2009.
  * [4] Kenneth L. Clarkson.  Subgradient and sampling algorithms for $\ell_{1}$ regression.  In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 257–266, 2005.
  * [5] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney.  Sampling algorithms and coresets for $\ell_{p}$ regression.  SIAM J. Comput., 38(5):2060–2078, 2009.
  * [6] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In STOC, pages 569–578. For an updated version, see http://arxiv.org/abs/1106.1379v1, 2011.
  * [7] Dan Feldman, Morteza Monemizadeh, and Christian Sohler.  A PTAS for $k$-means clustering based on weak coresets.  In SCG ’07: Proceedings of the twenty-third annual symposium on Computational geometry, pages 11–18, New York, NY, USA, 2007. ACM.
  * [8] Dan Feldman and Leonard J. Schulman.  Data reduction for weighted and outlier-resistant clustering.  In SODA, pages 1343–1354, 2012.
  * [9] Sariel Har-Peled and Soham Mazumdar.  On coresets for $k$-means and $k$-median clustering.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, STOC ’04, pages 291–300, New York, NY, USA, 2004. ACM.
  * [10] Michael Langberg and Leonard J. Schulman.  Universal $\epsilon$-approximators for integrals.  In SODA, pages 598–607, 2010.
  * [11] Michael W. Mahoney and Petros Drineas.  CUR matrix decompositions for improved data analysis.  Proceedings of the National Academy of Sciences, 106(3):697–702, 2009.
  * [12] Kasturi Varadarajan and Xin Xiao.  A near-linear algorithm for projective clustering integer points.  In SODA, pages 1329–1342, 2012.


# Interaction energy between a charged medium and its electromagnetic field as
a dark matter candidate

Mayeul Arminjon
Univ. Grenoble Alpes, CNRS, Grenoble INP, 3SR, F-38000 Grenoble, France

###### Abstract

In the scalar theory of gravitation with a preferred reference frame, a
consistent formulation of electrodynamics in the presence of gravitation needs
to introduce an additional energy tensor: the interaction energy tensor. This
energy is gravitationally active and might contribute to the dark matter,
because it has an exotic character and it is not localized inside matter. In
order to check if that energy might form representative dark halos, one has to
model the interstellar radiation field in a galaxy as a complete
electromagnetic field obeying the Maxwell equations. A model has been built
for this purpose, based on assuming axial symmetry and on recent results about
axisymmetric Maxwell fields. Its predictions for the variation of the spectral
energy density inside our Galaxy are relatively close to those of a recent
radiation transfer model, except on the symmetry axis of the Galaxy, where the
present model predicts extremely high values of the energy density.

##  1 Introduction

Our initial motivation for the present work was independent of the problem of
dark matter. It was to develop a consistent electrodynamics in an alternative
theory of gravity: “the scalar ether theory”, or SET. This is a preferred-
frame theory based on a scalar field only, [1, 2] that reduces to special
relativity (SR) when the gravitational field vanishes. In general relativity
(GR), the modification of the equations of electrodynamics in the presence of
a gravitational field consists simply in rewriting the equations that are
valid in SR, by using the “comma goes to semicolon” rule:$\quad{}_{,\,\nu}\
\rightarrow\ _{;\,\nu}$, i.e.: partial derivatives are replaced by covariant
derivatives based on the metric connection. (See Ref. [3] for an interesting
discussion.) In particular, the dynamical equation for the energy(-momentum-
stress) tensor ${{\boldsymbol{T}}}$ that is valid in SR is: $T^{\lambda\nu}_{\
\,,\nu}=0$. Using the rule mentioned above, that equation is modified to:
$T^{\lambda\nu}_{\ \,;\nu}=0$, which is indeed the dynamical equation in GR
and in many of its extensions or modifications. However, in the general
situation, the latter equation is not equivalent to the dynamical equation of
SET, [1] hence the foregoing rule cannot be used in SET.

Therefore, in that alternative theory, a different and less obvious path has
to be taken for the purpose of adaptating classical electrodynamics in the
presence of a gravitational field. It turns out that this leads to introduce
an exotic form of energy, and that this new form is a possible candidate for
dark matter. In this conference paper, we quickly follow that path. We then
summarize the Maxwell model of the interstellar radiation field, that we built
to prepare the test of this candidate.

##  2 Necessity of an interaction tensor in SET

In SET, we assume classically that the electromagnetic field tensor
${{\boldsymbol{F}}}$ derives from a 4-potential $A_{\mu}$:

${\color[rgb]{0.14,0.11,0.49}F_{\mu\nu}:=A_{\nu,\mu}-A_{\mu,\nu}=A_{\nu;\mu}-A_{\mu;\nu}}.$
(1)

This is (locally) equivalent to assuming that (i) ${{\boldsymbol{F}}}$ is
antisymmetric ($F_{\mu\nu}=-F_{\nu\mu\,})$ and (ii) the first group of the
Maxwell equations is satisfied:

${\color[rgb]{0.14,0.11,0.49}F_{\lambda\mu\,,\nu}+F_{\mu\nu,\lambda}+F_{\nu\lambda,\mu}\equiv
F_{\lambda\mu\,;\nu}+F_{\mu\nu;\lambda}+F_{\nu\lambda;\mu}=0.}$ (2)

(The first equality in (2) is indeed an identity due to the antisymmetry of
the field tensor and to the symmetry of the metric connection.) Therefore, in
SET, the first group of the Maxwell equations is left unchanged. In a first
version of electrodynamics in the presence of a gravitational field in SET,
the second group of the Maxwell equations was got by applying the dynamical
equation of SET to a charged medium in the presence of the Lorentz force,
assuming that the following holds for the energy tensors, as is the case in SR
and still in GR:

$\mathrm{(A)\ Total\ energy\ tensor}\
{\color[rgb]{0.14,0.11,0.49}{{\boldsymbol{T}}}={{\boldsymbol{T}}}_{\mathrm{charged\
medium}}+{{\boldsymbol{T}}}_{\mathrm{field}}}.$ (3)

(The total energy tensor ${{\boldsymbol{T}}}$ is the source of the
gravitational field — more precisely, in SET, that source is the component
$T^{00}$ in the preferred reference frame of the theory; see Ref. [1] for
details.) The additivity (3) leads to a form of Maxwell’s second group of
equations in SET. [4] But that form of Maxwell’s second group in SET predicts
charge production/destruction at untenable rates, therefore it has to be
discarded. [5] The additivity assumption (3) is contingent and may be
abandoned. This means introducing an “interaction” energy tensor
${{\boldsymbol{T}}}_{\mathrm{inter}}$, such that

${\color[rgb]{0.14,0.11,0.49}{{\boldsymbol{T}}}={{\boldsymbol{T}}}_{\mathrm{charged\
medium}}+{{\boldsymbol{T}}}_{\mathrm{field}}\
\underline{+{{\boldsymbol{T}}}_{\mathrm{inter}}}\,}.$ (4)

One then has to constrain the form of ${{\boldsymbol{T}}}_{\mathrm{inter}}$
and to derive equations for it.

##  3 Form of the interaction tensor

In SR, the additivity (3) of the energy tensors does apply, thus
${{\boldsymbol{T}}}_{\mathrm{inter}}={\bf 0}$. In SET we may impose that
${{\boldsymbol{T}}}_{\mathrm{inter}}$ should be Lorentz-invariant in the
situation of SR, i.e. when the metric ${{\boldsymbol{\gamma}}}$ is Minkowski’s
metric ${{\boldsymbol{\gamma}}}^{0}$ ($\gamma^{0}_{\mu\nu}=\eta_{\mu\nu}$ in
Cartesian coordinates). This is true if and, one can prove, [6] only if we
have:

${\color[rgb]{0.14,0.11,0.49}T_{\mathrm{inter}\
\mu\nu}=p\,\gamma^{0}_{\mu\nu}}\qquad\mathrm{(situation\ of\ SR)},$ (5)

with some scalar field $p$. This is equivalent to:

${\color[rgb]{0.14,0.11,0.49}T^{\mu}_{\mathrm{inter}\ \
\nu}=p\,\delta^{\mu}_{\nu}}\qquad\mathrm{(situation\ of\ SR)}.$ (6)

The definition

${\color[rgb]{0.14,0.11,0.49}T^{\mu}_{\mathrm{inter}\ \
\nu}:=p\,\delta^{\mu}_{\nu}},\qquad\mathrm{or}\quad{\color[rgb]{0.14,0.11,0.49}(T_{\mathrm{inter}})_{\mu\nu}:=p\,\gamma_{\mu\nu}},$
(7)

thus got in a Minkowski spacetime, is in fact generally-covariant. Hence, we
adopt (7) for the general case. With a general metric
${{\boldsymbol{\gamma}}}$, the tensor (7) is still pointwise Lorentz-invariant
— in the sense that we have
$(T_{\mathrm{inter}})_{\mu\nu}\,(X)=p(X)\,\eta_{\mu\nu}$ in any coordinates
that are Cartesian at a given event $X$, and this form remains invariant after
any coordinate transformation that is Lorentz at $X$, i.e., such that the
matrix $\left(\frac{\partial x^{\prime\mu}}{\partial x^{\nu}}(X)\right)$
belongs to the Lorentz group.

##  4 SET electrodynamics with the interaction tensor

With the additivity assumption (3) of the energy tensors, i.e.,
${{\boldsymbol{T}}}_{\mathrm{inter}}={\bf 0}$, the system of equations of
electrodynamics of SET is closed, but violates charge conservation. With the
interaction energy tensor (7) we have just one unknown more: the scalar field
$p$. So we need just one scalar equation more. It turns out to be consistent
to add charge conservation as the new scalar equation. [7] Then the system of
equations of electrodynamics of SET is again closed, and now it satisfies
charge conservation.

Based on that closed system, equations were derived that determine the field
$p$ in a given general electromagnetic (EM) field $({\bf E},{\bf B})$ and in a
given weak gravitational field with Newtonian potential $U$: [7] the scalar
field $p$ (or more exactly, its first approximation $p_{1}$) obeys an
advection equation:

${\color[rgb]{0.14,0.11,0.49}\partial_{T}\,p_{1}+u^{j}\partial_{j}\,p_{1}=S}.$
(8)

That equation has given source $S$ and given characteristic curves, the latter
being the integral curves $\mathcal{C}(T_{0},{\bf x}_{0})$ of the spatial
vector field ${\bf u}$ in Eq. (8). Here, “given” means that the source field
$S$, as also the vector field ${\bf u}$ and hence the characteristic curves
$\mathcal{C}(T_{0},{\bf x}_{0})$, do not depend on the unknown field $p_{1}$.
It follows that $p_{1}$ can be obtained by integrating the source field $S$
along those curves. [7]

The “medium” defined by the corresponding interaction energy tensor field
${{\boldsymbol{T}}}_{\mathrm{inter}}=p{{\boldsymbol{\gamma}}}$ can be counted
as “dark matter”, for

  * •

it is not localized inside (usual) matter: indeed, the equations for the field
$p_{1}$ show that its source $S$ is, in general, non-zero as soon as there is
a general EM field: ${\bf E}\neq 0,\ {\bf B}\neq 0,\ {\bf E.B}\neq 0$, and a
variable gravitational field with $\partial_{T}U\neq 0$, where the time
derivative $\partial_{T}U$ of the Newtonian potential is taken in the
preferred frame; [7]

  * •

it is gravitationally active, since, from its definition (4), it contributes
to the source of the gravitational field in SET, that is the component
$T^{00}$ in the preferred frame;

  * •

it is “exotic”, i.e., it is not usual matter — as shown by the form (7) of its
energy tensor, which is very different from the possible energy tensors of any
fluid, solid, or EM field. The fact that it is Lorentz-invariant means that no
velocity can be defined for that medium. The energy tensor (7) depends only on
one scalar field ($p$), hence no equation of state is needed.

The foregoing considerations are at the classical level, hence do not tell if
the “matter” with the energy tensor (7) is made of quantum particles.

##  5 Maxwell model of the ISRF

In order to check if the interaction energy $E_{\mathrm{inter}}$ might be
distributed in the form of dark halos and contribute significantly to the dark
matter distribution, we have to compute the field $p$ for a model of a galaxy.
This needs that we have a model of the Interstellar Radiation Field in a
galaxy (ISRF) that provides that field as a solution of the Maxwell equations.
However, the existing models of the ISRF (e.g. Refs. [8, 9, 10, 11, 12, 13])
focus on the radiation transfer (mainly via absorption, reemission or
scattering by dust particles). They follow the paths of light rays or photons.
To the best of our knowledge, no previous model of the ISRF did consider the
full EM field with its six interacting components subjected to the Maxwell
equations. Therefore, we had to build a model entirely from scratch, which
involved both theoretical and numerical difficulties. [17]

###  5.1 Maxwell model of the ISRF: Main assumptions

i) Axial symmetry is a relevant approximation for many galaxies, and is in
fact often used in the existing models of the ISRF (see e.g. Refs. [13, 14,
15, 16]). We adopt cylindrical coordinates $(\rho,\phi,z)$ whose the $z$ axis
is the symmetry axis.

The primary source of the ISRF is made of the stars or other bright
astrophysical objects. We want to describe the ISRF as a smoothed-out field at
the galactic scale, not the field in the stars or in their neighborhood.
Therefore:

ii) we consider the source-free Maxwell equations.

We proved the following result: [18]

Theorem. Any time-harmonic axisymmetric source-free Maxwell field is the sum
of two simple fields of that same kind:

  * •

1) one deriving from a vector potential ${\bf A}$ having just $A_{z}\neq 0$,
with $A_{z}$ a time-harmonic axisymmetric solution of the scalar wave
equation;

  * •

2) one deduced from a field of the form (1) by EM duality, i.e.

${\color[rgb]{0.14,0.11,0.49}{\bf E}^{\prime}=c{\bf B},\quad{\bf
B}^{\prime}=-{\bf E}/c}.$ (9)

###  5.2 Maxwell model of the ISRF: Form of the model

We consider an EM field having a finite set of frequencies $(\omega_{j})\
(j=1,...,N_{\omega})$. That EM field is thus the sum of $N_{\omega}$ time-
harmonic EM fields. Using the Theorem above, each of them is generated by
potentials $A_{jz},\,A^{\prime}_{jz}$. The scalar potential $A_{jz}$, for the
field of the form (1) above with frequency $\omega_{j}$, can be a priori any
time-harmonic axisymmetric solution of the scalar wave equation having
frequency $\omega_{j}$. [18] However, in the relevant “totally propagating”
case, such a solution can be written explicitly in terms of a spectrum
function $S_{j}=S_{j}(k)$ ($-K_{j}\leq k\leq K_{j}$,
$K_{j}:=\frac{\omega_{j}}{c}$): $A_{jz}=\psi_{\omega_{j}\,S_{j}}$, with [19]

${\color[rgb]{0.14,0.11,0.49}\psi_{\omega_{j}\
S_{j}}\,(t,\rho,z):=e^{-\operatorname{i}\omega_{j}t}\int_{-K_{j}}^{K_{j}}\
J_{0}\left(\rho\sqrt{K_{j}^{2}-k^{2}}\right)\
e^{\operatorname{i}k\,z}\,S_{j}(k)\,\operatorname{d}k},$ (10)

where $J_{0}$ is the Bessel function of the first kind and of order 0. The
“dual” potential $A^{\prime}_{jz}$, for the field of the form (2) above with
frequency $\omega_{j}$, has just the same form (10), with, in the general
case, another spectrum function, say $S^{\prime}_{j}$.

###  5.3 Maxwell model of the ISRF: Model of a galaxy

We model an axisymmetric galaxy as a finite set $\\{{\bf x}_{i}\\}$ of point-
like “stars”, the azimuthal distribution of which is uniform. That set of
points is obtained by pseudo-random generation of their cylindrical
coordinates $\rho,\phi,z$ with specific probability laws, ensuring that [17]

  * •

the distribution of $\rho$ and $z$ is approximately that valid for the star
distribution in the galaxy considered (in the numerical application, we took
our Galaxy);

  * •

the set $\\{{\bf x}_{i}\\}$ is approximately invariant under azimuthal
rotations of any angle $\phi$.

###  5.4 Maxwell model of the ISRF: Determining the potentials

To determine the potentials $A_{j\,z}$ and $A^{\prime}_{j\,z}$
($j=1,...,N_{\omega}$) that generate the model ISRF (Subsect. 5.2), we are
fitting to the form (10) a sum of spherical potentials emanating from the
“stars” at points ${\bf x}_{i}$, thus determining the unknown spectrum
functions $S_{j}$ and $S^{\prime}_{j}$. [17] For the purpose of this fitting,
every point-like “star” is indeed assumed to contribute spherical scalar waves
$\psi_{{\bf x}_{i}\,\omega_{j}}$ having the same frequencies $\omega_{j}$ as
has the model ISRF, and whose emission center is the spatial position ${\bf
x}_{i}$ of the star:

${\color[rgb]{0.14,0.11,0.49}\psi_{{\bf x}_{i}\,\omega_{j}}\ (t,{\bf
x}):=\psi_{\omega_{j}}\ (t,{\bf x}-{\bf
x}_{i})=\frac{e^{\operatorname{i}(K_{j}\,r_{i}-\omega_{j}t)}}{K_{j}\,r_{i}}}.$
(11)

Here $r_{i}:=\left|{\bf x}-{\bf x}_{i}\right|$, $K_{j}:=\frac{\omega_{j}}{c}$,
and the function

${\color[rgb]{0.14,0.11,0.49}\psi_{\omega_{j}}\ (t,{\bf
x})=\frac{e^{\operatorname{i}(K_{j}\,r-\omega_{j}t)}}{K_{j}\,r}},\qquad{\color[rgb]{0.14,0.11,0.49}r:=\left|{\bf
x}\right|}$ (12)

is (up to an amplitude factor) the unique time-harmonic solution of the scalar
wave equation, with frequency $\omega_{j}$, that has spherical symmetry around
${\bf x}={\bf 0}$ and that is an outgoing wave. Spherical symmetry is assumed
in order to ensure that all of the directions starting from the star are
equivalent, of course. Of course also, the uniqueness of the solution (12)
means the uniqueness of the solution translated from ${\bf x}={\bf 0}$ to
${\bf x}={\bf x}_{i}$: the function ${\color[rgb]{0.14,0.11,0.49}\psi_{{\bf
x}_{i}\,\omega_{j}}}$ given by Eq. (11). This implies that we cannot define
different contributions of the “star” at ${\bf x}_{i}$ to the $A_{j\,z}$
potential and to the “dual” potential $A^{\prime}_{j\,z}$, other than through
multiplying ${\color[rgb]{0.14,0.11,0.49}\psi_{{\bf x}_{i}\,\omega_{j}}}$ by
two different amplitude factors — for which there is no apparent reason.
Therefore, we actually must assume that $A_{j\,z}=A^{\prime}_{j\,z}$, thus
$S_{j}=S^{\prime}_{j}$, and our fitting problem writes

${\color[rgb]{0.14,0.11,0.49}\sum_{i=1}^{i_{\mathrm{max}}}\psi_{{\bf
x}_{i}\,\omega_{j}}\cong\psi_{\omega_{j}\ S_{j}}}\quad\mathrm{on}\
{\color[rgb]{0.14,0.11,0.49}G}\qquad({\color[rgb]{0.14,0.11,0.49}j=1,...,N_{\omega}}).$
(13)

Here the symbol $\cong$ indicates that the equality is in the sense of the
least-squares, the two sides being evaluated on some spatio-temporal grid $G$.
The unknown spectrum function $S_{j}$ is defined (approximately) by its values
$S_{nj}:=S_{j}(k_{nj})$ at a regular discretization
$k_{nj}=-K_{j}+n\frac{2K_{j}}{N}\ (n=0,...,N)$ of the integration interval
$[-K_{j},+K_{j}]$ for $k$ in the integral (10). [17] With this discretization,
(13) becomes the explicit least-squares system

${\color[rgb]{0.14,0.11,0.49}\sum_{i=1}^{i_{\mathrm{max}}}\psi_{{\bf
x}_{i}\,\omega_{j}}\cong\sum_{n=0}^{N}f_{nj}\,S_{nj}}\quad\mathrm{on}\
{\color[rgb]{0.14,0.11,0.49}G}{\color[rgb]{0.14,0.11,0.49}\qquad(j=1,...,N_{\omega})},$
(14)

with $f_{nj}(t,\rho,z)=\exp(-\operatorname{i}\omega_{j}t)\,g_{nj}(\rho,z)$ a
specific time-harmonic function. [20] The complex numbers $S_{nj}\
(n=0,...,N;\,j=1,...,N_{\omega})$ are the solved-for parameters. Note that
(14) defines $N_{\omega}$ fitting problems. Previously, a unique “grouped
fitting” was done: solving the least-squares system obtained by summing on the
frequency index $j$ on both sides of (14). [17] The “separate fitting” (14) is
more precise — and also less time-consuming, since actually the common
harmonic time dependence can be removed from both sides of (14), thus
eliminating the time variable, and hence considering only a spatial grid
$G^{\prime}$ instead of a spatio-temporal grid $G$. [20] The computer time is
indeed an important point to be considered, because a precision better than
quadruple must be implemented. [17]

###  5.5 Application to the spatial variation of the spectral energy density
in the Galaxy

Because we consider an EM field with a finite frequency spectrum
$(\omega_{j})\ (j=1,...,N_{\omega})$, each among its six components has the
following form:

${\color[rgb]{0.14,0.11,0.49}F^{(q)}(t,{\bf
x})={\mathcal{R}e}\left(\sum_{j=1}^{N_{\omega}}C^{(q)}_{j}({\bf
x})e^{-\operatorname{i}\omega_{j}t}\right)\qquad(q=1,...,6)}.$ (15)

It follows that the time-averaged volumic energy density of the field is given
by: [21]

${\color[rgb]{0.14,0.11,0.49}\overline{U}({\bf x}):=\overline{\frac{\delta
W}{\delta V}}({\bf x})=\sum_{j=1}^{N_{\omega}}u_{j}({\bf x}),\qquad u_{j}({\bf
x}):=\frac{1}{4}\sum_{q=1}^{6}\alpha_{q}\left|C^{(q)}_{j}({\bf
x})\right|^{2}},$ (16)

where $\alpha_{q}=\epsilon_{0}$ for an electric field component, whereas
$\alpha_{q}=\epsilon_{0}c^{2}$ for a magnetic field component (here
$\epsilon_{0}$ is the vacuum permittivity, with $\epsilon_{0}=1/(4\pi\times
9\times 10^{9})$ in SI units). Thus, the spectral energy density (SED) has a
discrete form.

Specializing to the present axisymmetric model, we thus have
$C^{(q)}_{j}=C^{(q)}_{j}(\rho,z)$ and $u_{j}=u_{j}(\rho,z)$. The potentials
$A_{jz}=A^{\prime}_{jz}=\psi_{\omega_{j}\,S_{j}}$ are determined by the
spectrum functions $S_{j}$ in Eq. (10), which are given in the numerical model
by the values $S_{nj}:=S_{j}(k_{nj})$, that are the output of the fitting.
These potentials generate the EM field, hence the $C^{(q)}_{j}(\rho,z)$
coefficients in Eq. (15) are expressed uniquely in terms of the $S_{nj}$ ’s.
[21] However, in the least-squares problem (14), the scalar radiations emitted
by every point-like “star” are taken to be exactly $\psi_{{\bf
x}_{i}\,\omega_{j}}$. Clearly, we may multiply the l.h.s. of (14) by some
number $\xi_{j}>0$, thus obtaining now new values
$S^{\prime}_{nj}=\xi_{j}S_{nj}\ (n=0,...,N)$ as the solution of (14). We
determine the numbers $\xi_{j}>0$ so that the SED measured at our local
position ${\bf x}_{\mathrm{loc}}$ in the Galaxy coincides with the calculated
values $u_{j}({\bf x}_{\mathrm{loc}})$. This allows us then to make
predictions: in particular, ones of the spatial variation of the SED in the
Galaxy, which we may compare with the predictions of the existing models of
the ISRF. Figures 1–2 show this comparison for the four positions in the
Galaxy for which the predicted SED is shown in Ref. [13]. The predictions of
the two models are quite reasonably close, although the SED predicted by the
present model has rather marked oscillations as function of the wavelength.
Note that the different wavelengths are fully uncoupled due to the “separate
fitting” defined by the $N_{\omega}$ least-square problems (14).

Figure 1: SEDs at ($\rho=1$ kpc, $z=0$) and at ($\rho=1$ kpc, $z=1\,$kpc).

Figure 2: SEDs at ($\rho=8$ kpc, $z=0$) and at ($\rho=8$ kpc, $z=1\,$kpc).

A surprising prediction of this model is that for the values of the maximum of
the energy density,

${\color[rgb]{0.14,0.11,0.49}u_{j\mathrm{max}}=\mathrm{Max}\\{u_{j}(\rho_{m},z_{p});\
m=1,...,N_{\rho},\ p=1,...,N_{z}\\}},$ (17)

found for the different spatial grids ($N_{\rho}\times N_{z}$) investigated,
all having $\rho$ varying regularly from $\rho_{0}=0$ to
$\rho_{\mathrm{max}}\simeq 10$ kpc and $z$ varying regularly from $z_{0}=0$ or
$z_{0}=-z_{\mathrm{max}}$ to $z_{\mathrm{max}}\leq 1\,$kpc. Figure 3 compares
the curves $u_{j\mathrm{max}}=f(\lambda_{j})$ found with two spatial grids. It
is seen that the two curves are quite close to one another, and both show
extremely high levels of $u_{j\mathrm{max}}$, from $10^{27}\mathrm{eV/cm}^{3}$
to $10^{21}\mathrm{eV/cm}^{3}$. This is confirmed by a rather detailed
investigation of the effects of the settings of the calculation (the spatial
grid, and also the fineness of the frequency mesh: $N_{\omega}$, and that of
the discretization: $N$). [20] The values of the maximum of $u_{j}$ are always
found on the axis of the Galaxy ($\rho=0$), moreover the level of $u_{j}$
decreases very rapidly when one departs from the axis. [20] This prediction of
the model may be described as a kind of self-focusing effect of the ISRF in an
axisymmetric galaxy.

Figure 3: Maximum of energy density; comparison between two spatial grids.

##  6 Conclusion

In the “scalar ether theory” of gravity (SET), a consistent electrodynamics in
a gravitational field needs the introduction of an additional energy tensor:
${{\boldsymbol{T}}}_{\mathrm{inter}}$, with $T^{\mu}_{\mathrm{inter}\ \
\nu}:=p\,\delta^{\mu}_{\nu}$. Thus, this energy tensor was not designed to
build missing mass. However, it turns out that the corresponding “medium”
could contribute to dark matter, for it is not localized inside matter, it is
gravitationally active, and it is “exotic”. Moreover, the scalar field $p$,
that determines ${{\boldsymbol{T}}}_{\mathrm{inter}}$, can be in principle
calculated from the data of the EM field and the gravitational field, through
explicit equations. This however demands to be able to model the EM field in a
galaxy, which is essentially in the form of the interstellar radiation field
(ISRF).

Therefore, we built a Maxwell model of the ISRF. This was motivated by the
foregoing, but it is also interesting independently of that, as the ISRF is a
very important physical characteristic of a galaxy and interacts strongly with
the cosmic rays. In any case, this model in itself is totally independent of
the theory of gravitation and the assumption about the interaction tensor. It
is based on an explicit representation of any time-harmonic axisymmetric
source-free Maxwell field through a pair of scalar potentials, and on
determining these potentials by fitting contributions emanating from a set of
point-like “stars” schematizing a galaxy. The predictions of the model for the
variation of the spectral energy distribution in the Galaxy are currently
being checked. They are relatively close to the predictions of a recent
radiation transfer model — except for the fact that the Maxwell model of the
ISRF predicts extremely high values of the energy density on the axis of the
Galaxy, that however decrease very rapidly when departing from that axis. We
hope to be able in a future work to apply the model to calculate the
interaction energy and to check if its distribution resembles a dark halo.

## References

  * [1] M. Arminjon, Space isotropy and weak equivalence principle in a scalar theory of gravity, Braz. J. Phys. 36, 177–189 (2006).
  * [2] M. Arminjon and R. W. Winkler, Motion of a test particle according to the scalar ether theory of gravitation and application to its celestial mechanics, Z. Naturforsch. A 74, 305–316 (2019).
  * [3] H. Stephani, Relativity, An Introduction to Special and General Relativity, Third edition (Cambridge University Press, Cambridge, 2004), pp. 156–158.
  * [4] M. Arminjon, Continuum dynamics and the electromagnetic field in the scalar ether theory of gravitation, Open Phys. 14, 395–409 (2016).
  * [5] M. Arminjon, Charge conservation in a gravitational field in the scalar ether theory, Open Phys. 15, 877–890 (2017).
  * [6] M. Arminjon, Lorentz-invariant second-order tensors and an irreducible set of matrices, J. Geom. Symmetry Phys. 50, 1–10 (2018).
  * [7] M. Arminjon, On the equations of electrodynamics in a flat or curved spacetime and a possible interaction energy, Open Phys. 16, 488–498 (2018).
  * [8] B. T. Draine, Photoelectric heating of interstellar gas, Astrophys. J. Suppl. Ser. 36, 595–619 (1978).
  * [9] J. S. Mathis, P. G. Mezger and N. Panagia, Interstellar radiation field and dust temperatures in the diffuse interstellar matter and in giant molecular clouds, Astron. Astrophys. 128, 212–229 (1983).
  * [10] X. Chi and A. W. Wolfendale, The interstellar radiation field: a datum for cosmic ray physics, J. Phys. C: Nucl. Part. Phys. 17, 987–998 (1991).
  * [11] K. D. Gordon, K. A. Misselt, A. N. Witt and G. C. Clayton, The DIRTY model. I. Monte Carlo radiative transfer through dust, Astrophys. J. 551, 269–276 (2001).
  * [12] T. P. Robitaille, HYPERION: an open-source parallelized three-dimensional dust continuum radiative transfer code, Astron. Astrophys. 536, A79, 17 pages (2011).
  * [13] C. C. Popescu, R. Yang, R. J. Tuffs, G. Natale, M. Rushton and F. Aharonian, A radiation transfer model for the Milky Way: I. Radiation fields and application to High Energy Astrophysics, Mon. Not. Roy. Astr. Soc. 470, no. 3, 2539–2558 (2017).
  * [14] N. D. Kylafis and J. N. Bahcall, Dust distribution in spiral galaxies, Astrophys. J. 317, 637–645 (1987).
  * [15] T. A. Porter and A. W. Strong, A new estimate of the galactic interstellar radiation field between $0.1\mu$m and $1000\mu$m, in Proc. 29th International Cosmic Ray Conference Pune (Tata Institute of Fundamental Research, Mumbai, 2005), vol. 4, pp. 77–80.
  * [16] C. C. Popescu, R. J. Tuffs, M. A. Dopita, J. Fischera, N. D. Kylafis and B. F. Madore, Modelling the spectral energy distribution of galaxies. V. The dust and PAH emission SEDs of disk galaxies, Astron. Astrophys. 527, A109, 40 pages (2011).
  * [17] M. Arminjon, An analytical model for the Maxwell radiation field in an axially symmetric galaxy, Open Phys. 19, 77–90 (2021).
  * [18] M. Arminjon, An explicit representation for the axisymmetric solutions of the free Maxwell equations, Open Phys. 18, 255–263 (2020).
  * [19] M. Zamboni-Rached, E. Recami and H. E. Hernández-Figueroa, Structure of nondiffracting waves and some interesting applications, in Localized Waves, eds. H. E. Hernández-Figueroa, M. Zamboni-Rached, E. Recami (John Wiley & Sons, Hoboken, 2008), pp. 43–77.
  * [20] M. Arminjon, Interstellar radiation as a Maxwell field: improved numerical scheme and application to the spectral energy density, Preprint HAL-03341905 (2021).
  * [21] M. Arminjon, Spectral energy density in an axisymmetric galaxy as predicted by an analytical model for the Maxwell field, Adv. Astron. 2021, 5524600, 13 pages (2021).