# Trust the Process: Zero-Knowledge Machine Learning to Enhance Trust in
Generative AI Interactions

Bianca-Mihaela Ganescu1, Jonathan Passerat-Palmbach1, 2

###### Abstract

Generative AI, exemplified by models like transformers, has opened up new
possibilities in various domains but also raised concerns about fairness,
transparency and reliability, especially in fields like medicine and law. This
paper emphasizes the urgency of ensuring fairness and quality in these domains
through generative AI. It explores using cryptographic techniques,
particularly Zero-Knowledge Proofs (ZKPs), to address concerns regarding
performance fairness and accuracy while protecting model privacy. Applying
ZKPs to Machine Learning models, known as ZKML (Zero-Knowledge Machine
Learning), enables independent validation of AI-generated content without
revealing sensitive model information, promoting transparency and trust. ZKML
enhances AI fairness by providing cryptographic audit trails for model
predictions and ensuring uniform performance across users. We introduce
snarkGPT, a practical ZKML implementation for transformers, to empower users
to verify output accuracy and quality while preserving model privacy. We
present a series of empirical results studying snarkGPT’s scalability and
performance to assess the feasibility and challenges of adopting a ZKML-
powered approach to capture quality and performance fairness problems in
generative AI models.

## Introduction

The latest developments in Generative AI have opened new possibilities for AI
to become more pervasive in multiple fields. For example, GPT-4 can now pass
internationally recognized exams in medicine and law (Nori et al. 2023; OpenAI
2023). Such advancements in transformer-based models introduce new challenges,
particularly in ensuring the uniform quality and execution of these models for
all users when deployed and accessed through remote cloud APIs. This notion is
commonly known as performance fairness (Jiang et al. 2023).

Over the past few years, the field of AI fairness has witnessed substantial
progress in addressing bias mitigation within machine learning models. This
collective effort has yielded methods that strive to create fairer models,
reducing the impact of biases in various applications. This paper explores a
novel algorithmic approach that complements AI fairness strategies by focusing
on ensuring the uniform performance and execution of deployed AI models across
users.

We present a protocol that empowers users to engage with remote servers
hosting AI models, ensuring that the model they interact with behind a black-
box API is indeed the precise model they have requested from the provider.

The implications of this approach extend across domains, with particular
relevance in fields such as healthcare and finance, where the outcomes
produced by AI models can profoundly affect the well-being of end-users,
especially those belonging to underrepresented populations.

Our approach leverages zkSNARKs (Zero-Knowledge Succinct Non-interactive
ARgument of Knowledge), a cryptographic tool that bolsters the integrity of
computations while preserving user privacy by not disclosing sensitive
information during the verification process.

Recent developments have given rise to a burgeoning body of research known as
ZKML (Zero-Knowledge Machine Learning) (Feng et al. 2021; Lee et al. 2020;
Kang et al. 2022), which focuses on leveraging zkSNARKs to verify the
integrity of the inference pass in AI models. ZKML serves two primary
purposes:

  1. 1.

Verification of Model Output: In scenarios where users submit their data to
remote services hosting AI models, ZKML provides users with a cryptographic
proof that the output they receive originates from the exact model they have
requested or paid for. This is particularly pertinent in Generative AI
applications like ChatGPT, where multiple subscription tiers promise varying
levels of model performance. Currently, users lack guarantees that the output
aligns with their subscription tier.

  2. 2.

Enhancing Data Privacy: ZKML is also valuable for enhancing data privacy. In
cases where users are unwilling or unable to upload their data to remote
third-party models, model owners can deploy models directly to users’ devices.
While this deployment strategy is unproblematic in scenarios like predictive
text on a smartphone keyboard, more sensitive situations exist, such as
financial services’ Know Your Customer (KYC) processes. ZKML enables model
providers to confidently deploy their models to users’ devices, ensuring that
the model’s predictions are genuinely derived from their model and not
simulated by the user using alternative software. The combination of data
locality and the Zero-Knowledge property preserves user data privacy.

In the context of AI fairness, ZKML directly contributes to performance
fairness, ensuring that all users of a particular service experience
consistent quality. Model owners need not reveal their model’s weights,
preserving their valuable intellectual property. Instead, they can publish a
model fingerprint that is verified as an additional step during user output
generation. This has far-reaching implications, including addressing equality
of outcomes concerns in applications like credit scoring models, which have
faced criticism for perpetuating discrimination against underrepresented
communities, such as racial minorities. By employing ZKML, banks can make
their creditworthiness assessments fully transparent and trustworthy,
guaranteeing that the same model is used for all users. Auditors can evaluate
model decisions alongside the proof provided by users disputing their scores,
thereby eliminating discrimination rooted in users’ backgrounds.

The remainder of this paper demonstrates the viability of our approach. In the
background section, we introduce “snarkGPT,” a verifiable ZKML pipeline. In
the evaluation section, we provide empirical results that underscore the
effectiveness of our approach, specifically showcasing its applicability to a
GPT2-size model.

## Background

### zkSNARKs

Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs)
(Bitansky et al. 2017) represent advanced cryptographic tools that allow
verifying the correctness of a computation without revealing the inputs or
intermediate steps. The foundation of zkSNARKs is rooted in a rich
mathematical framework characterised by their advantageous properties,
including zero-knowledge, succinctness, non-interactivity, argument soundness,
knowledge-soundness, and completeness.

In the field of verifiable computing (VC), zkSNARKs offer an effective
solution by enabling clients to delegate computationally intensive tasks to
providers. After delegation, the provider (prover) sends a concise
cryptographic proof to the client (verifier), allowing the client to verify
the correctness of the computation without the need for a full re-
execution(Petkus 2019). Most notably, the size of the proof is significantly
smaller than the size of the original computation. This succinct proof size is
a fundamental characteristic of zkSNARKs, making them suitable for situations
where executing the whole computation is not feasible, as is the case for
generative AI. Moreover, in scenarios involving outsourced AI computations,
zkSNARKs provide a robust mechanism for clients to verify the correctness of
model inferences without compromising data confidentiality. This is
particularly relevant in the context of secure model inference-as-a-service.

To describe zkSNARKs for generative AI, we can define them formally as, given
a function evaluation $f(x;w)=y$, where $x$ is a public input, $w$ is a
private input called witness and $y$ the output, zkSNARKs allow the prover to
generate a proof $\pi$ such that the verifier that knows $x$, $y$ and $\pi$
can check that the prover knows $w$ such that $f(x;w)=y$ (Kang et al. 2022).
For example, in the case of transformers, $x$ can represent an input prompt,
$w$ the model weights and $y$ the output of executing the model using input
prompt $x$ and weights $w$.

Most zkSNARK protocols proceed in three steps (Nitulescu 2020):

  1. 1.

Arithmetisation: producing a system of polynomial equations over a large prime
field (an arithmetic circuit) for which finding a solution is equivalent to
computing $f(x;w)$. Therefore, given $(f,y,x,w)$, the circuit constraints are
met if and only if $y=f(x;w)$.

  2. 2.

Building an information-theoretic proof system, that is, building a proof
system that guarantees soundness even against a computationally unbounded
prover. This system usually relies on idealized components (oracles) or is
inefficient.

  3. 3.

Compiling the information-theoretic proof system into an efficient one using
cryptographic tools at the cost of considering only computationally bounded
adversaries.

There are two main classes of zkSNARKs: Quadratic Arithmetic Program
(QAP)-based and Polynomial Interactive Oracle Proof (PIOP)-based. QAP-based
zkSNARKs utilize arithmetic circuits and divisibility checks. PIOP-based
zkSNARKs compile circuits into polynomial constraints and employ polynomial
commitment schemes. Recent years have seen a dominance of PIOP-based SNARKs
mainly due to their increased flexibility.

This work uses one of the most popular and well-documented PIOP-based proof
systems: Halo2.

#### Halo2

Halo2 (hal ) is an instance of a PIOP made non-interactive via the Fiat-Shamir
heuristic (Fiat and Shamir 1987). The scheme uses Plonkish arithmetisation
(Gabizon, Williamson, and Ciobotaru 2019) to represent a relation and a
satisfying witness to that relation as a low-degree polynomial. Then, the
constructed polynomial is fed into a polynomial commitment scheme where the
prover commits to the polynomial and can evaluate it provably at arbitrary
points from the verifier. Halo2 uses the inner product argument (Bowe, Grigg,
and Hopwood 2019) as a polynomial commitment scheme. However, other frameworks
using Halo2 can choose to have a different commitment scheme, as is the case
of EZKL (introduced subsequently in the background section) using KZG (Kate,
Zaverucha, and Goldberg 2010). Using Halo2, a verifier can use an accumulation
scheme to batch instances it wants to evaluate.

Plonkish arithmetisation allows polynomial constraints with certain restricted
forms of randomness and supports custom gates and lookup arguments. Plonkish
arithmetisation conceptualises the arithmetic circuit as a matrix (referred to
as circuit matrix) of m columns and n rows over a given finite field
$\mathbb{F}$ (therefore, the cells contain elements of $\mathbb{F}$). Each
column j encodes a wire and corresponds to a Lagrange interpolation polynomial
$p_{j}(X)$ over the powers (rows) of an $n^{th}$ primitive of unity $\omega$
that evaluates to $p_{j}(\omega^{i})=x_{ij}$. A permutation argument is used
to enforce the equality of cells.

The matrix defines a sequence of polynomial constraints, which are
multivariate polynomials over $\mathbb{F}$ that must evaluate to zero for each
row. In a polynomial constraint, the variables can refer to a cell in a given
column of the current row or another row relative to this one.

To improve performance, Halo2 can trade memory for CPU by pre-computing and
storing lookup tables for some part of the computation. The lookup argument
enforces a relation between variables, where the relation is expressed as a
table. The lookup table consists of two advice columns and two fixed columns
of the matrix, where every expression in the set of advice columns is equal to
some expression in the set of fixed columns. Therefore, the lookup argument is
a more permissive version of the permutation argument. It enforces that all
the input-output pairs in the witness are valid input-output pairs in the
fixed columns. Lookup tables are often leveraged to represent more complex
arithmetic relationships in the circuit matrix that would otherwise be hard to
capture only with additions and multiplications. A prime example is non-
linearities in neural networks that would otherwise have to be numerically
approximated.

#### EZKL

EZKL (Camuto and Morton 2022, 2023) is a Rust library and command-line tool
that allows constructing zkSNARKs for the inference phase of machine-learning
models. EZKL uses Halo2 with KZG in the backend, with certain modifications
that make the library compatible with larger models, compared to existing
solutions implementing zkSNARKs for machine learning models. EZKL converts
pre-trained models from ONNX to Halo2 circuit matrices. Instead of directly
implementing each of the 100+ ONNX operations individually, EZKL builds upon
the tract library (Sonos 2020), which reduces and prunes complex ONNX graphs
to compositions of a smaller set of operations. By leveraging the Einstein
summation operation, EZKL can represent numerous linear operations such as
matrix multiplication, dot product, transposition, and tensor contraction with
a single operation. This approach allows EZKL to support a wide range of
models, including those with LSTM and self-attention layers while only having
to support 20 operations as equivalent circuit constraints. Notably, EZKL
improves the memory costs of the Halo2 circuit matrix by allocating additional
columns if all of the available rows have been filled. By the definition of
Halo2, there can be arbitrarily many columns in the circuit matrix, but the
number of rows has to be a power of 2. This comes at the cost of increasing
the proving time.

### Generative AI: from GPT down to nanoGPT

Text generation within generative AI relies on advanced models such as
Transformers, introduced in 2017 (Radford et al. 2018), which have since
become foundational for language models. The architecture consists of 12
transformer blocks with masked multi-head self-attention. GPT-2 and GPT-3 are
improved versions with larger datasets and more parameters.

GPT-2 largely follows the architecture of GPT-1 and has four trained models
available for use, each having a different number of blocks and embedding
sizes. Their number of parameters are 117M, 345M, 762M and 1.5B, respectively.
GPT-3 (Radford et al. 2019) follows the same architecture as GPT-2, with a few
hyperparameters modified to improve performance. The model has configurations
ranging from 175M to 175B parameters. GPT-4 extends this line of models and
accepts multiple modalities, but its authors have yet to document its
architecture thoroughly in a peer-reviewed publication.

In this work, we focus on the GPT-2 architecture (the same as the GPT-3
architecture), as it is the latest architecture in the GPT series for which a
Python implementation has been made public at the time of writing. We propose
a zkSNARK for the transformer architecture as a proof-of-concept, using
nanoGPT: a smaller version of the GPT-2 architecture. NanoGPT’s code aims to
be shorter and easier to interpret (Karpathy 2022, 2020), but remains
compatible with the original GPT-2 and can be used to train or finetune
medium-sized GPTs.

## Related work

### ZKML

Previous research has proposed zkSNARK protocols or the inference phase of
smaller neural networks. Lee et al. (Lee et al. 2020) propose a protocol for
verifiable convolutional neural networks, using QAP-based zkSNARKs for pooling
and ReLU, QPP (Quadratic Polynomial Program)-based zkSNARKs for convolutions
and CP(Commit-and-Prove)-SNARKs for interconnecting the layers. They argue
that their scheme improves the key generation/proving time by 25X compared to
the state-of-the-art zkSNARK scheme (Groth 2016) for a small example of the
MNIST model consisting of a single convolutional layer with ReLU and a single
pooling layer. Moreover, for VGG16, they argue that their scheme improves the
performance by 1800X, compared with (Groth 2016).

Another approach was proposed by Weng et al. (Weng et al. 2022), for privacy-
preserving and verifiable CNNs by using a modified version of QAP - QMP
(Quadratic Matrix Program). The authors use a QMP-based arithmetic circuit to
express convolutional relations and generate zkSNARKs proofs based on
Homomorphic Encryption (HE) and collaborative inference, which promises to
protect both the model and the data privacy. They argue that they obtain 17.6X
faster Setup time and 13.9X faster proving time than the QAP-based method in
their experiments.

ZEN is an optimizing compiler for verifiable neural networks using zkSNARKs,
introduced by Feng et al. (Feng et al. 2021). It proposes two privacy-
preserving, verifiable inference schemes for neural networks, $ZEN_{acc}$ and
$ZEN_{infer}$, which promise to provide privacy guarantees for both the model
and the data. The authors also introduce two optimizations for R1CS: R1CS
friendly quantization, which they argue "brings up to 73.9$\times$ savings in
R1CS constraints for a convolution layer and up to 8.4$\times$ reduction for
fully connected kernel without any additional accuracy loss" ((Feng et al.
2021), page 2), and Stranded encoding of R1CS Constraints, which they argue
"leads to up to 2.2$\times$ improvement in R1CS constraints for convolution
kernel and 3.4$\times$ improvement for fully connected kernel" ((Feng et al.
2021), page 2).

Kang et al. (Kang et al. 2022) followed the steps of EZKL and also constructed
Halo2 proofs for verifying the inference phase of a machine learning model.
They propose an ImageNet-scale (Deng et al. 2009) zkSNARK using Halo2 and
present three protocols for verifying the ML model accuracy, verifying the ML
model predictions and trustless retrieval of items matching a predicate,
respectively. They argue that they can achieve up to 79% accuracy on ImageNet-
scale while simultaneously taking as few as 10s and 5,952 bytes to verify and
that the zkSNARK can be scaled down to take as few as 0.7s to verify at 59%
accuracy. Comparing their results to (Lee et al. 2020), (Weng et al. 2022),
(Feng et al. 2021) and (Liu, Xie, and Zhang 2021), they claim that the proving
time for the prior work is at least 10X higher than their Halo2 method and up
to 1,000X higher.

### Fairness

Fairness has garnered significant attention within the field of machine
learning, encompassing a wide range of investigations into the unintended
behaviours exhibited by machine learning models (Barocas, Hardt, and Narayanan
2017). The literature has extensively explored various facets of fairness,
including the concepts of group fairness and performance fairness. The former
strives to mitigate model bias with respect to specific protected attributes
(Du et al. 2021; Gálvez et al. 2021; Chu et al. 2021), while the latter
necessitates the uniformity of performance distributions across different
recipients (Zhang, Kou, and Wang 2020; Deng, Kamani, and Mahdavi 2020;
Pentyala et al. 2022). This section concentrates on the notion of performance
fairness.

Performance fairness has garnered particular prominence within Federated
Learning, wherein client data originating from multiple sources exhibits high
heterogeneity and spans geographical diversity. Mohri et al. introduced an
initial framework for optimizing the performance of the poorest-performing
device through a minimax optimization scheme (Mohri, Sivek, and Suresh 2019).
Subsequently, the q-FedAvg algorithm was introduced by Li et al. (Li et al.
2020), offering a more flexible optimization objective tailored to achieve
varying degrees of fairness. More recently, Ditto was introduced as an
approach to engender fairness by enabling the learning of personalized models
(Li et al. 2021).

As we can see, the works mentioned above primarily centre on narrowing the
performance gap across heterogeneous clients. This pursuit aligns with our
approach, which is complementary. Our method empowers clients to identify and
conscientiously report performance fairness disparities without compromising
the sensitivity and confidentiality of their private data.

## A provably fair GPT prototype: SNARKGPT

This section describes ZKML in the context of performance fairness and how
zkSNARKs can ensure that all clients of a generative AI service are treated
equally. We demonstrate the practical viability of this solution by
introducing snarkGPT, a verifiable ZKML pipeline for the GPT-2 model, and
suggest an accompanying protocol to capture potential fairness deviations.

### A protocol fostering performance fairness

In the context of remote service hosting generative AI models, we set the
challenge for a provider to instil confidence in consumers regarding the
uniform quality and execution of the models it serves.

Starting from a simple case, we question how a premium user (or institution)
of ChatGPT can obtain the guarantee that they use the premium version of the
model at all times and not a cheaper version sometimes. With the growing
popularity of ChatGPT, it is unclear how the service deals with the high
number of requests. At the moment of writing, the only option for paying users
is to trust that OpenAI always serves the premium model to premium users.

One option is for the model provider to share the model weights. However, this
poses problems. Sharing these weights means leaking substantial intellectual
property encapsulated within these models, and not all users may have the
necessary computing power to use these weights effectively (Butler 2023).

We believe that a promising solution to the lack of guarantees in these cases
is using zkSNARKs, which can prove, beyond a reasonable doubt, the correct
execution of a computation. Indeed, as discussed in the related work section,
previous work has proposed zkSNARKs solutions for verifying the correct
execution and accuracy of other machine learning models, such as CNNs, DNNs
and ImageNet-scale.

One possible ZKML protocol is as follows:

  1. 1.

The provider of a generative AI model publishes a commitment (for example, a
hash) to the model weights using a Credible Commitment Device (Kalai et al.
2010) (for instance in a public domain).

  2. 2.

A client can then send some input data to the provider and ask the provider to
evaluate the model on that input data.

  3. 3.

The provider generates the output of the model evaluated on the client’s data,
as usual, and generates a zkSNARK. The proof takes as parameters the weights
of the model (private), the client’s input data (public) and the output of the
model (public). The zkSNARK enables anyone to validate the correct execution
of the model with significantly smaller costs. The proof attests that the
model produces the reported output given the parameters above and the public
commitment to the model.

  4. 4.

The client can then run a verification protocol to accept or reject the proof
without access to the model weights.

To evaluate the viability of ZKML to equip generative AI with performance
fairness and quality guarantees, we introduce "snarkGPT", a zkSNARK prototype
for the GPT-2 architecture in the following sections.

### nanoGPT adaptations

Table 1: The architecture of the nanoGPT model (Karpathy 2022). Layer |  Parameters |  Role
---|---|---
Token Embedding |  vocabulary size,embedding size |  Creates token embeddings for the input sequence.
Positional Embedding |  block size,embedding size |  Creates positional embeddings for the input sequence.
Dropout |  dropout rate |  Takes as input the token and positional embeddings and zeroes rate% random elements.
List[Transformer Blocks] |  number of layers |  The model’s hidden layers/transformer blocks. Takes as input the token and positional embeddings after dropout.
Layer Normalisation |  embedding size |  Applies Layer Normalization to the output of the hidden layers, as described in (Ba, Kiros, and Hinton 2016).
Language Modelling Head (Linear Layer) |  embedding size,vocabulary size |  A linear layer with weights tied to the input embedding.

The architecture of the nanoGPT model is illustrated in table 1. The model
takes in as input an input prompt, which can be empty, and generates text
based on the input sequence. Anchoring this setting to a medical diagnosis, a
patient’s symptoms represent the input prompt, and the medical prescription
represents the generated text. To achieve quality guarantees, we must adapt
the nanoGPT model to make it compatible with zkSNARKs.

First, since zkSNARKs operate over finite fields, all model values must be
mapped to a value in the chosen finite field. In the self-attention mechanism
of transformers, the elements in the upper-triangular portion of the self-
attention matrix are set to $-\inf$ to eliminate the information that follows
in the sequence. $-\inf$ is not a valid element of a finite field. Therefore,
we set the elements in the upper-triangular portion of the self-attention
matrix to the smallest value covered in the Halo2 lookup table. More
specifically, let $B$ be the lookup table’s logarithmic size. The lookup table
stores all values in the given finite field between $-2^{B-1}+1$ and
$2^{B-1}-1$. Thus, we zero out the elements in the self-attention matrix by
setting them to $-2^{B-1}+1$. Then, we remove all optimizations that are not
compatible with ONNX (flash attention (Dao et al. 2022)) nor EZKL (array
slicing, cube operation). Note that these operations are only used in the
nanoGPT python code to accelerate computing self-attention on GPU. Removing
them has thus no impact on the accuracy of the model.

## Empirical feasibility evaluation

### Overview

This part of the study aims to shed light on the feasibility of our
cryptographic solution for complementing fairness in machine learning models,
specifically focusing on nanoGPT. As the time and memory costs for the
verifier are constant in Halo2, we evaluate the performance of our proposed
method based on the time and memory costs for the prover, who has to generate
the zkSNARK proof. The server hosting the model would bear the burden of
generating the proof when the user wants to obtain quality guarantees for the
service they’re consuming. Our experiments provide empirical evidence of the
overhead and challenges in adopting ZKML as a de facto approach to improve
performance fairness in a client-server setting.

We first test to what extent we can scale up two of the main components of our
nanoGPT architecture when generating the proof: the number of layers and the
size of the embeddings. We consider these parameters in our tests because they
are core parameters of the self-attention mechanism. To be able to focus on
the parameters we select to increase, we choose relatively small values for
the rest of the parameters for simplicity. More specifically, we set the
vocabulary size to 65, the block size to 64, the number of heads to 4, the
batch size to 1 and the dropout rate to 0. All our tests are performed using a
fixed version of the EZKL framework (commit
8f122bf111https://github.com/zkonduit/ezkl/commit/8f122bf2eb5794b681364eb182d7cdd8a7350fe4).
We perform all our experiments on a machine with the following specifications:
Intel i7-9700K CPU, 3.60 GHz / 4.90 GHz, 64 GB 3600 MHz RAM and 200 GB Swap
area in NVMe SSD.

We are also interested in how the circuit size (the log number of rows pre-
allocated for the Halo2 circuit matrix to represent the model) influences the
time and memory costs for the prover. Therefore, in our tests, we create
multiple proofs for the same nanoGPT model configuration using EZKL, wherein
we systematically vary the logarithmic dimensions allocated to the matrix
representation of the circuit. We expect that a larger matrix will result in
significantly higher proving costs.

### Scaling Up the Model

Tables LABEL:table:scaleUpEmbeddings and LABEL:table:scaleUpLayers present a
detailed breakdown of the runtime incurred during proof generation for varying
embedding sizes and layers, respectively. As shown in Tab.
LABEL:table:scaleUpEmbeddings, the computational demands appear to increase
nonlinearly with the size of the embeddings. For instance, the proof
generation time increases from $\sim$5 minutes for an embedding size of 64 to
$\sim$20 minutes for an embedding size of 144. Similarly, an augmentation in
the number of layers corresponds to an increase in the time required for proof
generation. These combined results emphasize the complex factors that must be
considered when optimizing the architecture of generative AI models within
cryptographic frameworks. ZKML practitioners must balance the model’s
representational capacity with a tractable computational efficiency. In other
words, the findings highlight the need for a nuanced approach that considers
both the sophistication of the model’s representation and the practical
constraints imposed by zkSNARKs.

### Circuit Matrix Size Impact on Proof Generation

Table LABEL:table:MemoryImpact illustrates the impact of the (logarithmic)
size of the circuit matrix representation of the nanoGPT model on proof
generation time and memory costs. That is, the number of rows we have to pre-
allocate in memory for the circuit matrix representation when using EZKL and
Halo2. As illustrated, the runtime exhibits a non-linear progression,
initially improving from 3 minutes and 55 seconds to 3 minutes and 11 seconds
as the logarithmic size increases from 14 to 18. However, beyond this point,
there is a notable rise in runtime, with a substantial increase observed for a
matrix logarithmic size of 24 and 25. The increased runtime for larger circuit
matrices aligns with our expectations. Suppose we allocate significantly more
rows in the matrix than needed for the number of polynomial constraints. In
that case, those rows will be filled with 0s and still be used in the process
(as each column describes a wire in the circuit), adding overhead.

Similarly, an upward trend in memory cost is apparent as the logarithmic size
of the circuit matrix increases. This is expected, as the entire matrix
representation of the circuit is generated and stored in RAM when generating
the proof. Notably, the memory cost experiences a more significant escalation
than the runtime, reaching 148 GB for a matrix logarithmic size of 25. This
finding underscores the intricate considerations involved in managing memory
resources when dealing with larger circuit matrices.

### Generalisation beyond GPT architectures

In this section, we present the empirical results of our investigation into
the relationship between a model’s architecture, the number of parameters and
the number of constraints generated within zkSNARK proofs. The number of
constraints directly reflects the proving costs. It is thus crucial in our
context to understand how generalizable our results are to other models beyond
generative LLMs.

#### Experimental Setup

To assess the generality of the parameter-constraint relationship, we designed
experiments based on a model configuration previously examined in Modulus Labs
(Labs 2023). This configuration consists of multiple Multi-Layer Perceptron
(MLP) layers, each comprising a linear layer, the Rectified Linear Unit (RELU)
activation function, and a scaling-down factor. We selected this setup to
assess if the observed parameter-constraint correlation extends to transformer
models like nanoGPT.

#### Results

Our empirical findings reveal a striking contrast in constraint generation
between nanoGPT and the Modulus Labs MLP model. Specifically, while the number
of constraints (M) in the zkSNARK proof for the Modulus Labs model roughly
aligns with the number of parameters (N) in the model, our nanoGPT model
exhibits a significantly higher M / N ratio, ranging from approximately 58X to
85X more constraints than parameters. These observations are summarized in
Table 5.

Notably, transformers such as nanoGPT exhibit a pronounced M / N ratio
increase. For instance, with an embedding size of 64, the M / N ratio
approximates 64. In practical terms, a one-million-parameter model generates a
staggering 64 million constraints, while a 250,000-parameter model still
generates 16 million constraints. In stark contrast, a four-layer
convolutional network with 3,047 parameters generates merely 13,152
constraints, yielding an M / N ratio of approximately 4.

#### Factors Impacting Constraint Generation

We recognize that the time and memory costs associated with zkSNARK proof
generation depend not only on the number of parameters but also on various
architectural and methodological factors. Specifically, the M / N ratio within
a ZK-circuit is influenced by 1) the specific gates and constraints chosen to
represent neural network layers; 2) the network architecture, as we have seen
from the difference between transformers and other types of networks; 3) the
chosen proof system and its embedded features, such as lookup arguments that
may yield fewer constraints than those without.

Addressing the challenge of minimizing this M / N ratio in zkSNARK proof
generation remains an open area of research and exploration. Our findings
underscore the need for innovative architectural designs and proof
methodologies to enhance the efficiency and practicality of our cryptographic
solution for fairness in machine learning models.

## Conclusion

This work introduced a pioneering approach that leverages Zero-Knowledge
Machine Learning (ZKML) to address the critical issues of performance fairness
and reliability in generative AI models. By harnessing zkSNARKs, our protocol
empowers users to confidently engage with AI models through remote cloud APIs,
ensuring that the model they interact with aligns precisely with their
expectations.

The practical viability of our proposal is demonstrated through "snarkGPT," a
verifiable ZKML pipeline for GPT2-like models. Our empirical evaluations
indicate the effectiveness of our approach, particularly in scaling up the
model and its generalization beyond GPT architectures. We showed how snarkGPT
could be inserted in an end-to-end protocol where the user could obtain a
proof of correct execution alongside the model’s regular output and verify it
in constant time regardless of the input size or model complexity.

This paper lays the foundation for a new era of transparent and reliable AI,
emphasizing ZKML as a vital component in guaranteeing quality and achieving
performance fairness. By leveraging ZKML, we bridge the gap between AI model
providers and users, ensuring that AI is a truly equitable and transparent
tool for all.

Table 2: Runtime during proof generation for nanoGPT configured with different embedding sizes. embeddings size | 64 | 80 | 96 | 112 | 128 | 144
---|---|---|---|---|---|---
Runtime for proof generation | 5m 2s | 6m 7s | 8m 33s | 11m 46s | 16m 9s | 20m 28s
Table 3: Runtime during proof generation for nanoGPT configured with different layer configurations. number of layers | 4 | 8 | 12 | 16 | 20
---|---|---|---|---|---
Runtime for proof generation | 5m 2s | 8m 30s | 12m 19s | 17m 4s | 29m 9s
Table 4: Time and memory costs incurred during proof generation for nanoGPT for different sizes of the circuit matrix. log size of the circuit matrix | 14 | 16 | 18 | 20 | 22 | 24 | 25
---|---|---|---|---|---|---|---
Runtime for proof generation | 3m 55s | 3m 26s | 3m 11s | 3m 34s | 4m 40s | 9m 53s | 14m 26s
Memory cost for proof generation | 44 GB | 45 GB | 46 GB | 49 GB | 63 GB | 118 GB | 148 GB
Table 5: The results of generating a zkSNARK proof for our nanoGPT model versus the Modulus Labs model. | Number of parameters | Runtime | Memory cost | Number of Constraints
---|---|---|---|---
| 0.2 M | 5m 2s | 63 GB | 17 M
| 0.31 M | 6m 7s | 76 GB | 24 M
nanoGPT | 0.45 M | 8m 33s | 108 GB | 34 M
| 0.79 M | 11m 46s | 132 GB | 45 M
| 1.01 M | 16m 9s | 173 GB | 58 M
| 0.2 M |  |  | 0.2 M
| 0.31 M |  |  | 0.3 M
MLP | 0.45 M |  $\sim$1m 30s |  $\sim$26 GB | 0.45 M
| 0.79 M |  |  | 0.8 M
| 1.01 M |  |  | 1 M

## References

  * (1) ????  The halo2 Book.  https://zcash.github.io/halo2/.  Accessed: 2023-01-25.
  * Ba, Kiros, and Hinton (2016) Ba, J. L.; Kiros, J. R.; and Hinton, G. E. 2016.  Layer normalization.  _arXiv preprint arXiv:1607.06450_.
  * Barocas, Hardt, and Narayanan (2017) Barocas, S.; Hardt, M.; and Narayanan, A. 2017.  Fairness in machine learning.  _NIPS tutorial_ , 1: 2.
  * Bitansky et al. (2017) Bitansky, N.; Canetti, R.; Chiesa, A.; Goldwasser, S.; Lin, H.; Rubinstein, A.; and Tromer, E. 2017.  The hunting of the SNARK.  _Journal of Cryptology_ , 30(4): 989–1066.
  * Bowe, Grigg, and Hopwood (2019) Bowe, S.; Grigg, J.; and Hopwood, D. 2019.  Recursive Proof Composition without a Trusted Setup.  Cryptology ePrint Archive, Paper 2019/1021.  https://eprint.iacr.org/2019/1021.
  * Butler (2023) Butler, A. 2023.  Building Trust in AI with Zero-knowledge proofs (ZKP).
  * Camuto and Morton (2022) Camuto, A. D.; and Morton, J. 2022.  EZKL.  https://github.com/zkonduit/ezkl.  Accessed: 2023-06-19.
  * Camuto and Morton (2023) Camuto, A. D.; and Morton, J. 2023.  What is EZKL?  https://docs.ezkl.xyz/.  Accessed: 2023-06-19.
  * Chu et al. (2021) Chu, L.; Wang, L.; Dong, Y.; and et al. 2021.  Fedfair: Training fair models in cross-silo federated learning.  _arXiv preprint arXiv:2109.05662_.
  * Dao et al. (2022) Dao, T.; Fu, D. Y.; Ermon, S.; Rudra, A.; and Ré, C. 2022.  FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.  arXiv:2205.14135.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_. Ieee.
  * Deng, Kamani, and Mahdavi (2020) Deng, Y.; Kamani, M. M.; and Mahdavi, M. 2020.  Distributionally robust federated averaging.  In _NeurIPS_ , volume 33, 15111–15122.
  * Du et al. (2021) Du, W.; Xu, D.; Wu, X.; and Tong, H. 2021.  Fairness-aware agnostic federated learning.  In _SDM_ , 181–189. SIAM.
  * Feng et al. (2021) Feng, B.; Qin, L.; Zhang, Z.; Ding, Y.; and Chu, S. 2021.  ZEN: An optimizing compiler for verifiable, zero-knowledge neural network inferences.  _Cryptology ePrint Archive_.
  * Fiat and Shamir (1987) Fiat, A.; and Shamir, A. 1987.  How to prove yourself: Practical solutions to identification and signature problems.  In _Advances in Cryptology—CRYPTO’86: Proceedings 6_ , 186–194. Springer.
  * Gabizon, Williamson, and Ciobotaru (2019) Gabizon, A.; Williamson, Z. J.; and Ciobotaru, O. 2019.  Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge.  _Cryptology ePrint Archive_.
  * Gálvez et al. (2021) Gálvez, B. R.; Granqvist, F.; van Dalen, R.; and Seigel, M. 2021.  Enforcing fairness in private federated learning via the modified method of differential multipliers.  In _NeurIPS Workshop Privacy in Machine Learning_.
  * Groth (2016) Groth, J. 2016.  On the Size of Pairing-based Non-interactive Arguments.  Cryptology ePrint Archive, Paper 2016/260.  https://eprint.iacr.org/2016/260.
  * Jiang et al. (2023) Jiang, M.; Roth, H. R.; Li, W.; Yang, D.; Zhao, C.; Nath, V.; Xu, D.; Dou, Q.; and Xu, Z. 2023.  Fair Federated Medical Image Segmentation via Client Contribution Estimation.  (arXiv:2303.16520).  ArXiv:2303.16520 [cs].
  * Kalai et al. (2010) Kalai, A. T.; Kalai, E.; Lehrer, E.; and Samet, D. 2010.  A commitment folk theorem.  _Games and Economic Behavior_ , 69(1): 127–137.
  * Kang et al. (2022) Kang, D.; Hashimoto, T.; Stoica, I.; and Sun, Y. 2022.  Scaling up Trustless DNN Inference with Zero-Knowledge Proofs.
  * Karpathy (2020) Karpathy, A. 2020.  Karpathy/minGPT: A minimal pytorch re-implementation of the openai GPT (generative pretrained transformer) training.  https://github.com/karpathy/minGPT.  Accessed: 2023-06-19.
  * Karpathy (2022) Karpathy, A. 2022.  Karpathy/nanoGPT: The simplest, fastest repository for training/finetuning medium-sized GPTs.  https://github.com/karpathy/nanoGPT.  Accessed: 2023-06-19.
  * Kate, Zaverucha, and Goldberg (2010) Kate, A.; Zaverucha, G. M.; and Goldberg, I. 2010.  Constant-size commitments to polynomials and their applications.  In _Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16_ , 177–194. Springer.
  * Labs (2023) Labs, M. 2023.  The Cost of Intelligence.  https://drive.google.com/file/d/1tylpowpaqcOhKQtYolPlqvx6R2Gv4IzE/view.  Accessed: 2023-06-19.
  * Lee et al. (2020) Lee, S.; Ko, H.; Kim, J.; and Oh, H. 2020.  vCNN: Verifiable convolutional neural network based on zk-SNARKs.  _Cryptology ePrint Archive_.
  * Li et al. (2021) Li, T.; Hu, S.; Beirami, A.; and Smith, V. 2021.  Ditto: Fair and robust federated learning through personalization.  In _ICML_ , 6357–6368.
  * Li et al. (2020) Li, T.; Sanjabi, M.; Beirami, A.; and Smith, V. 2020.  Fair resource allocation in federated learning.  In _ICLR_.
  * Liu, Xie, and Zhang (2021) Liu, T.; Xie, X.; and Zhang, Y. 2021.  zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy.  Cryptology ePrint Archive, Paper 2021/673.  https://eprint.iacr.org/2021/673.
  * Mohri, Sivek, and Suresh (2019) Mohri, M.; Sivek, G.; and Suresh, A. T. 2019.  Agnostic federated learning.  In _International Conference on Machine Learning_ , 4615–4625. PMLR.
  * Nitulescu (2020) Nitulescu, A. 2020.  zk-SNARKs: A Gentle Introduction.  Technical report, Technical report.
  * Nori et al. (2023) Nori, H.; King, N.; McKinney, S. M.; Carignan, D.; and Horvitz, E. 2023.  Capabilities of gpt-4 on medical challenge problems.  _arXiv preprint arXiv:2303.13375_.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774.
  * Pentyala et al. (2022) Pentyala, S.; Neophytou, N.; Nascimento, A.; De Cock, M.; and Farnadi, G. 2022.  Privfairfl: Privacy-preserving group fairness in federated learning.  _arXiv preprint arXiv:2205.11584_.
  * Petkus (2019) Petkus, M. 2019.  Why and How zk-SNARK Works.  arXiv:1906.07221.
  * Radford et al. (2018) Radford, A.; Narasimhan, K.; Salimans, T.; Sutskever, I.; et al. 2018.  Improving language understanding by generative pre-training.
  * Radford et al. (2019) Radford, A.; Wu, J.; Child, R.; Luan, D.; Amodei, D.; Sutskever, I.; et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8).
  * Sonos (2020) Sonos. 2020.  Tract: Tiny, no-nonsense, self-contained, tensorflow and ONNX inference.  Accessed: 2023-06-19.
  * Weng et al. (2022) Weng, J.; Weng, J.; Tang, G.; Yang, A.; Li, M.; and Liu, J. 2022.  pvCNN: Privacy-Preserving and Verifiable Convolutional Neural Network Testing.  _CoRR_ , abs/2201.09186.
  * Zhang, Kou, and Wang (2020) Zhang, D. Y.; Kou, Z.; and Wang, D. 2020.  Fairfl: A fair federated learning approach to reducing demographic bias in privacy-sensitive classification models.  In _Big Data_ , 1051–1060. IEEE.


# Generalized Outer Bounds on the Finite Geometric Sum of Ellipsoids

Navid Hashemi, Justin Ruths The authors are with the Department of Mechanical
Engineering at the University of Texas at Dallas, 800 W. Campbell Rd,
Richardson, TX, USA. Email: (navid.hashemi<EMAIL_ADDRESS>
###### Abstract

General results on convex bodies are reviewed and used to derive an exact
closed-form parametric formula for the boundary of the geometric (Minkowski)
sum of $k$ ellipsoids in $n$-dimensional Euclidean space. Previously this was
done through iterative algorithms in which each new ellipsoid was added to an
ellipsoid approximation of the sum of the previous ellipsoids. Here we provide
one shot formulas to add $k$ ellipsoids directly with no intermediate
approximations required. This allows us to observe a new degree of freedom in
the family of ellipsoidal bounds on the geometric sum. We demonstrate an
application of these tools to compute the reachable set of a discrete-time
dynamical system.

##  I INTRODUCTION

Ellipsoidal bounds are efficient representations of sets as they have various
appealing properties and require the tuning of relatively few parameters
compared with other representations. The convenience of ellipsoids, however,
also brings conservatism through the over-approximation of exact sets. For
this reason methods tend to seek to identify the most representative
ellipsoidal bounds, by finding optimal ellipsoidal bounds by minimizing, for
example, the volume. This task is particularly challenged when the exact set
is the geometric, or Minkowski, sum of multiple ellipsoids. Although the
geometric sum of convex sets is itself a convex set, the geometric sum of
several ellipsoids is not, in general, an ellipsoid [1, 2]. Motivated by the
ellipsoid sums that arise in the calculation of reachable sets in dynamical
systems, in this paper we provide a parameterized expression for the exact
boundary of the geometric sum of $k$ ellipsoids as well as a closed form
solution for an outer ellipsoidal bound.

Although it is straightforward to define the concept of the geometric sum, it
is challenging to quantify the result in closed form to be used, for example,
as part of a design problem. There are a variety of results in the literature
on the characterization of the geometric sum and difference for two or three
dimensional ellipsoids, e.g., see [3]. In addition the geometric sum has been
deeply studied for polygons (two dimension) and polyhedra (three dimension),
e.g., see [4, 5, 6, 7, 8]. The related algorithms are mainly based on either
the computation of the convolution of geometric boundaries [4] or
polygon/polyhedra decompositions [5, 6, 7, 8]. Sums of curved regions/surfaces
have also been studied [9, 10, 11, 12]. Here in this work, we provide novel
one shot proofs to recover known results in the systems and control literature
[13] regarding outer bounding ellipsoids of geometric sums of ellipsoids. The
new perspective offered by these proofs allows us to generalize several of
these existing results. We specifically show the existence of a new term
(degree of freedom) in parameterizing the family of ellipsoids that provide
tight outer bounds on the actual geometric sum.

We leverage the proposed results to compute outer ellipsoidal approximations
for the reachable set of a discrete-time linear control system subject to
ellipsoidally-bounded input sets. Such calculations, to date, have been done
iteratively and require calculating an outer ellipsoid approximation after the
addition of each ellipsoid [13]. Here, we propose an approach which computes
the geometric sum all in one step, which yields a closed-form characterization
of the ellipsoid bound and also reveals the opportunity to generalize the
existing results.

##  II Geometric Sum

In this work, we demonstrate how to specify the exact boundary of the
geometric sum of multiple ellipsoidally bounded sets.

######  Definition 1.

[14] The geometric (or Minkowski) sum of two convex sets
$\mathcal{S}_{1},\mathcal{S}_{2}\subset\mathbb{R}^{n}$ is

$\mathcal{S}_{1}\oplus\mathcal{S}_{2}=\left\\{s_{1}+s_{2}\ \Big{|}\
s_{1}\in\mathcal{S}_{1},\,s_{2}\in\mathcal{S}_{2}\right\\}.$ (1)

Note that while the geometric sum of two ellipsoids is a convex set, it is in
general not an ellipsoid.

###  II-A Exact Boundary of a Geometric Sum

A central tool in working with geometric operations on convex sets is the
support function,

$\rho(\ell|\mathcal{H})=\sup_{x\in\mathcal{H}}\langle\ell,x\rangle,$ (2)

which can be interpreted as the largest projection of elements in the convex
set $\mathcal{H}$ onto the direction given by the unit vector $\ell$.
Containment of one convex set within another convex set,
$\mathcal{H}\subset\mathcal{S}$, is exactly captured by the support function
of the contained set being less than or equal to the support function of the
containing set over all choices of $\ell$,

$\rho(\ell|\mathcal{H})\leq\rho(\ell|\mathcal{S}),\qquad\forall\ell\in\mathbb{R}^{n}.$
(3)

In addition, the support function of a geometric sum of two convex sets can be
expressed as the sum of their support functions [13]. The geometric sum of $k$
ellipsoids centered at zero with shape matrices $Q_{1},\dots,Q_{k}$ (see Fig.
1) is then

$\rho(\ell|\mathcal{H})=\sum_{i=1}^{k}\rho\big{(}\ell\,|\,\mathcal{E}(Q_{i})\big{)},$
(4)

where the ellipsoid with shape matrix $Q$ is given by

$\mathcal{E}(Q)=\left\\{\xi\ |\ \xi^{T}Q^{-1}\xi\leq 1\right\\}.$ (5)

When the convex sets of interest are ellipsoids, the support function can
further be expressed as

$\rho\big{(}\ell\,|\,\mathcal{E}(Q)\big{)}=\langle\ell,Q\ell\rangle^{\frac{1}{2}}.$
(6)

Therefore, the geometric sum (4) can be written as

$\rho(\ell|\mathcal{H})=\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}.$
(7)

Figure 1: Convex set $\mathcal{H}$ as a geometric sum of $k$ ellipsoids. Here
the ellipsoids are decreasing in size as would be the case for a stable
dynamical system and ellipsoids generated by (32).

The following result provides a closed form formula to calculate the exact
boundary of the geometric sum of a finite collection of ellipsoids based on
their support functions. Existing approaches approach the sum of a finite
collection of ellipsoids in an iterative fashion, in which the $j$-th
ellipsoid is geometrically summed with the result of the sum of ellipsoids $1$
through $j-1$. Although this iterative approach yields the same results in
some cases, we illustrate in this paper that our proposed “one-shot” approach
provides additional insight. Throughout the paper we will use the notation
$\overline{1,k}=\\{1,2,\dots,k\\}$.

######  Theorem 1.

Consider the set of $k$ ellipsoids characterized by the positive definite
matrices $Q_{i}\in\mathbb{V}^{n\times n}$, $i\in\overline{1,k}$. The exact
convex shape of their geometric sum is,
$\mathcal{H}=\bigoplus_{i=1}^{k}\mathcal{E}(Q_{i})$ with boundary

$\partial\mathcal{H}=\left\\{x\ \bigg{|}\
x=\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{-\frac{1}{2}}Q_{i}\ell,\
\forall\ell\in\mathcal{B}_{1}(0)\right\\},$ (8)

where $\mathcal{B}_{1}(0)$ is the unit ball in $\mathbb{R}^{n}$.

Proof: One way to interpret the support function (2) is that $\ell$ provides
the normal vector of the hyperplane that is tangent to the convex set
$\mathcal{H}$ at the point $x$. By the definition of the geometric sum, the
boundary point $x$ can be written as the sum of elements
$x_{i}\in\mathcal{E}(Q_{i})$ for $i\in\overline{1,k}$,

$\textstyle x=\sum_{i=1}^{k}x_{i},$ (9)

where each $x_{i}$ is a boundary point on each individual ellipsoid, i.e., the
maximizer of

$\rho\big{(}\ell\,|\,\mathcal{E}(Q_{i})\big{)}=\sup_{\xi\in\mathcal{E}(Q_{i})}\langle\ell,\xi\rangle,$
(10)

analogous to (2). Hence, for each $i\in\overline{1,k}$, $\ell$ provides the
(unit) normal vector of the hyperplane that is tangent to the ellipsoid
$\mathcal{E}(Q_{i})$ at the point $x_{i}$. The normal vector of the ellipsoid
can also be expressed as the gradient of the level set
$x_{i}^{T}Q_{i}^{-1}x_{i}=1$, hence,

$\textstyle\ell=\frac{\nabla(x_{i}^{T}Q_{i}^{-1}x_{i}-1)}{\|\nabla(x_{i}^{T}Q_{i}^{-1}x_{i}-1)\|}=\frac{Q_{i}^{-1}x_{i}}{\sqrt{x_{i}^{T}Q_{i}^{-2}x_{i}}}.$
(11)

If we use again the fact that $x_{i}^{T}Q_{i}^{-1}x_{i}=1$,

$\displaystyle\ell$
$\displaystyle=\textstyle\frac{(x_{i}^{T}Q_{i}^{-1}x_{i})Q_{i}^{-1}x_{i}}{\sqrt{x_{i}^{T}Q_{i}^{-2}x_{i}}}=x_{i}^{T}\frac{Q_{i}^{-1}x_{i}}{\sqrt{x_{i}^{T}Q_{i}^{-2}x_{i}}}Q_{i}^{-1}x_{i}$
$\displaystyle=x_{i}^{T}\ell Q_{i}^{-1}x_{i}.$ (12)

Note that as the maximizer of (10), the projection of $x_{i}$ onto $\ell$
gives the support function,

$x_{i}^{T}\ell=\rho(\ell\,|\,\mathcal{E}(Q_{i}))=\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}.$
(13)

Substituting (13) into (12) yields

$\ell=\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}Q_{i}^{-1}x_{i}.$ (14)

Finally, solving for $x_{i}$ and plugging these into (9) completes the proof.
$\blacksquare$

###  II-B Ellipsoidal Outer Bounds of the Geometric Sum

Because the exact boundary specified by Theorem 1 is a function of $\ell$ and
because it is in general not an ellipsoid, we are typically interested in
computing an outer bound on this exact set, which helps to maintain
tractability in many settings.

Theorem 2 characterizes the general family of shape matrices that provide an
outer ellipsoidal bound on the exact geometric sum, i.e.,
$\mathcal{H}\subseteq\mathcal{E}(Q)$. This result is similar to Theorem 2.7.1
in [13], which computes the geometric sum of $k$ ellipsoids through pairwise
sums. The recursive approach in [13] approximates the geometric sum of two
ellipsoids with an ellipsoid at each iteration which, as we will show through
the introduction of the matrix $Q_{0}$, fundamentally restricts the choice of
the outer bound.

######  Theorem 2.

Consider the set of $k$ ellipsoids characterized by the positive definite
matrices $Q_{i}\in\mathbb{V}^{n\times n}$, $i\in\overline{1,k}$. The ellipsoid
$\mathcal{E}(Q)$ is an outer bound of their geometric sum
$\mathcal{H}=\bigoplus_{i=1}^{k}\mathcal{E}(Q_{i})$, i.e.,
$\mathcal{H}\subseteq\mathcal{E}(Q)$, if

$\displaystyle Q$ $\displaystyle=Q_{0}+Q_{u},$ (15) $\displaystyle Q_{u}$
$\displaystyle=\sum_{i=1}^{k}Q_{i}+\sum_{i,j\in\mathcal{I}}p_{ij}Q_{i}+p_{ij}^{-1}Q_{j},$

where $p_{ij}>0\ \forall(i,j)\in\mathcal{I}=\\{(i,j)\ |\ 1\leq i<j\leq k,\
i,j\in\mathbb{N}\\}$ and $Q_{0}$ satisfies the following characteristics:

  1. 1.

$Q_{0}+Q_{u}>0$,

  2. 2.

$\langle\ell,(Q_{0}+Q_{u})\ell\rangle^{\frac{1}{2}}\geq\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}},\
\forall\ell\in\mathcal{B}_{1}(0)$.

Proof: To prove that the convex set of the geometric sum is bounded by the
ellipsoid, i.e., $\mathcal{H}\subseteq\mathcal{E}(Q)$, it suffices to prove
(3) holds between the support functions $\rho(\ell|\mathcal{E}(Q))$ and
$\rho(\ell|\mathcal{H})$. We first define a positive coefficient $p_{ij}$
between the shape matrices $Q_{i}$ and $Q_{j}$ and in order to avoid
redundancy assume $i<j$, which constructs the set $\mathcal{I}$. Given a unit
vector $\ell$, we start with the following sum of squares which is always
nonnegative

$\sum_{i,j\in\mathcal{I}}\left(\sqrt{p_{ij}}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}-\sqrt{p_{ij}}^{-1}\langle\ell,Q_{j}\ell\rangle^{\frac{1}{2}}\right)^{2}\geq
0.$ (16)

Expanding this series results in

$\sum_{i,j\in\mathcal{I}}\left(p_{ij}\langle\ell,Q_{i}\ell\rangle+p_{ij}^{-1}\langle\ell,Q_{j}\ell\rangle\right)\geq\sum_{i,j\in\mathcal{I}}2\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}\langle\ell,Q_{j}\ell\rangle^{\frac{1}{2}}.$

Now we add $\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle$ to both sides and add
$\langle\ell,Q_{0}\ell\rangle$ to the left side of the inequality. Since
$Q_{0}$ satisfies the two conditions presented in the theorem, the inequality
still holds,

$\displaystyle\langle\ell,Q_{0}\ell\rangle+\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle+\sum_{i,j\in\mathcal{I}}p_{ij}\langle\ell,Q_{i}\ell\rangle+p_{ij}^{-1}\langle\ell,Q_{j}\ell\rangle$
$\displaystyle\geq\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle+\sum_{i,j\in\mathcal{I}}2\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}\langle\ell,Q_{j}\ell\rangle^{\frac{1}{2}}.$
(17)

This allows us to complete the square on the right hand side of the
inequality. The left hand side, then, becomes the definition of $Q$ in (15),
such that it is equal to $\langle\ell,Q\ell\rangle$. Therefore,
$\langle\ell,Q\ell\rangle\geq\big{(}\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}\big{)}^{2}$,
which means,

$\underbrace{\langle\ell,Q\ell\rangle^{\frac{1}{2}}}_{\rho\big{(}\ell\,|\,\mathcal{E}(Q)\big{)}}\geq\underbrace{\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}}_{\rho(\ell|\mathcal{H})},$
(18)

and the underbrace definitions come from (6) and (7). We conclude then that
$\mathcal{H}\subseteq\mathcal{E}(Q)$ from (3). $\blacksquare$

Although it is written in several terms in (15), the shape matrix $Q$ is a
linear combination of the individual shape matrices $Q_{i}$,
$Q=Q_{0}+\sum_{i=1}^{k}\alpha_{i}Q_{i}$, with coefficients $\alpha_{i}$ that
are the combination of $p_{ij}$ and $p_{ij}^{-1}$. If the coefficients of the
$Q_{i}$ are too large or if $Q_{0}$ is positive definite, then it makes
$\mathcal{E}(Q)$ a loose outer bound on $\mathcal{H}$. The former occurs when
$p_{ij}$ is either very large or very small (so $p_{ij}^{-1}$ is large). Thus
to have a tight outer bound, which is tangent to the exact sum $\mathcal{H}$,
the challenge is to select the definition of $p_{ij}$ appropriately. This
insight is largely already captured in analogous results that exist in the
literature [13]. What is novel here, is the additional degree of freedom
provided by $Q_{0}$. A tempting trivial solution is to select $Q_{0}=0$,
however, we will show in Section II-C that this choice prohibits the minimum
trace bounding ellipsoid from being a tight outer bound on the exact geometric
sum.

Figure 2: There are an infinite number of ellipsoids that are a tight outer
bound of a convex set $\mathcal{H}$, each tangent to $\mathcal{H}$ at
different points (corresponding to different choices of the unit vector
$\ell$). Since many of these tight ellipsoids can actually be quite
misleading, we assert that the minimum trace ellipsoid produces the most
representative outer bound.

In the current literature, the family of tight (tangent) outer ellipsoidal
bounds on the geometric sum is parameterized by a choice of $\ell$ [14],

$Q=\left(\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}\right)\left(\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{-\frac{1}{2}}Q_{i}\right).$
(19)

The choice of $\ell$ changes where the outer bound is tangent to the actual
geometric sum (see Fig. 2). Here, in Corollary 3 we show that the one-step
approach provided by Theorems 1 and 2 enable a more general formulation of the
family of tangent ellipsoid outer bounds than is provided in (19).

######  Corollary 3.

Consider the set of $k$ ellipsoids characterized by the positive definite
matrices $Q_{i}\in\mathbb{V}^{n\times n}$, $i\in\overline{1,k}$. Given a unit
vector $\ell\in\mathbb{R}^{n}$ the ellipsoids $\mathcal{E}(Q)$ with

$\displaystyle Q$ $\displaystyle=Q_{0}+Q_{\ell},$ (20) $\displaystyle
Q_{\ell}$
$\displaystyle=\left(\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}\right)\left(\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{-\frac{1}{2}}Q_{i}\right),$

provide all possible ellipsoidal bounds that touch the boundary of the
geometric sum $\mathcal{H}=\bigoplus_{i=1}^{k}\mathcal{E}(Q_{i})$, i.e.,
$\mathcal{H}\subseteq\mathcal{E}(Q)$, and are tangent at the respective points

$x=\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{-\frac{1}{2}}Q_{i}\ell.$ (21)

and where $Q_{0}$ satisfies the following characteristics:

  1. 1.

$Q_{0}+Q_{\ell}>0$,

  2. 2.

$\ell\in\ker(Q_{0})$,

  3. 3.

$\langle\tilde{\ell},(Q_{0}+Q_{\ell})\tilde{\ell}\rangle^{\frac{1}{2}}\geq\sum_{i=1}^{k}\langle\tilde{\ell},Q_{i}\tilde{\ell}\rangle^{\frac{1}{2}},\
\forall\tilde{\ell}\in\mathcal{B}_{1}(0)$.

Proof: This corollary can be derived either from Theorem 1 or 2. For
completeness we provide both as they provide different insight.

Based on Theorem 2, the outer bound is tangent to the exact geometric sum if
(18) holds with equality for some $\ell$, which in turn requires (16) and (17)
to hold with equality. The former occurs when the $p_{ij}>0$ coefficients are
selected as

$p_{ij}=\frac{\langle\ell,Q_{j}\ell\rangle^{\frac{1}{2}}}{\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}}.$
(22)

Substituting (22) into (15) results in (20). For (17) to hold with equality,
we also require $\langle\ell,Q_{0}\ell\rangle=0$, which leads to the new
condition on $Q_{0}$, $\ell\in\ker(Q_{0})$.

Based on Theorem 1, given a unit vector $\ell$ the corresponding point on the
boundary of the geometric sum is given by (21). For the ellipsoid
$\mathcal{E}(Q)$ to touch the boundary of the geometric sum at this point we
equate the support function of the outerbounding ellipsoid (6) with the
support function of the geometric sum (7),

$\langle\ell,Q\ell\rangle^{\frac{1}{2}}=\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}.$
(23)

Using the same approach as in Theorem 1 (see (14)), we find the relationship
between the tight ellipsoidal bound shape matrix, $Q$, the point of tangency
$x$, and the direction $\ell$ as,

$\ell=\underbrace{\langle\ell,Q\ell\rangle^{\frac{1}{2}}}_{\text{\eqref{eq:subsetequality}}}Q^{-1}\underbrace{x}_{\text{\eqref{eq:exactreachableset2}}}.$
(24)

Making the substitutions in the underbraces, multiplying both sides by $Q$,
and factoring out $\ell$ yields

$\displaystyle Q\ell$
$\displaystyle=\left[\left(\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{\frac{1}{2}}\right)\left(\sum_{i=1}^{k}\langle\ell,Q_{i}\ell\rangle^{-\frac{1}{2}}Q_{i}\right)\right]\ell.$

As a positive definite shape matrix, $Q$ is invertible, which leads to the
definition of $Q$ in (20), where $Q_{0}$ satisfies the proposed conditions.
$\blacksquare$

Like Theorem 2, Corollary 3 establishes the existence of a set of symmetric
matrices $Q_{0}$ that modify the shape matrices provided in (19), with the
trivial choice $Q_{0}=0$ resulting directly to (19). While in this work we do
not specify $Q_{0}$ any further than the conditions listed in Theorem 2 or
Corollary 3, it clarifies that the existing characterization of shape matrices
omit the additional degree of freedom provided by $Q_{0}$.

###  II-C Minimum Trace Ellipsoidal Outer Bound

Figure 2 easily demonstrates that a tight ellipsoidal bound does not
necessarily provide a representative outer bound for a convex set. Even
ellipsoids that minimize volume can lead to highly eccentric bounding
ellipsoids. The minimum trace ellipsoid tends to produce a more representative
outer bound. The trace of the shape matrix is the sum of the eigenvalues and
the lengths of the principal axes of the ellipsoid are the singular values.
Thus, by minimizing the trace it penalizes long principal axes. We denote this
minimum trace ellipsoid by $\mathcal{E}(Q^{*})$. A further benefit of this
choice is that facilitates an analytic expression for its shape matrix, which
is derived in Lemma 4.

######  Lemma 4.

Consider the set of $k$ ellipsoids characterized by the positive definite
matrices $Q_{i}\in\mathbb{V}^{n\times n}$, $i\in\overline{1,k}$. The ellipsoid
$\mathcal{E}(Q^{*})$ is an outer bound of their geometric sum
$\mathcal{H}=\bigoplus_{i=1}^{k}\mathcal{E}(Q_{i})$, i.e.,
$\mathcal{H}\subseteq\mathcal{E}(Q^{*})$, where

$\displaystyle Q^{*}$
$\displaystyle=\left(\sum_{i=1}^{k}\sqrt{\mathrm{tr}(Q_{i})}\right)\left(\sum_{i=1}^{k}\frac{Q_{i}}{\sqrt{\mathrm{tr}(Q_{i})}}\right).$
(25)

Specifically, of all the shape matrices that correspond to ellipsoid outer
bounds of $\mathcal{H}$ using Theorem 2 with $Q_{0}=0$, $Q^{*}$ has the
minimum trace.

Proof: Taking $Q_{0}=0$ and starting from the general condition on $p_{ij}$
for $\mathcal{E}(Q)$ to be an outer bound, (15) of Theorem 2, we take the
trace operation of both sides

$\mathrm{tr}(Q)=\sum_{i=1}^{k}\mathrm{tr}(Q_{i})+\sum_{i,j\in\mathcal{I}}p_{ij}\mathrm{tr}(Q_{i})+p_{ij}^{-1}\mathrm{tr}(Q_{j}),$
(26)

making $\mathrm{tr}(Q)$ a function of $p_{ij}$, $(i,j)\in\mathcal{I}$. To find
the minima, we find the stationary points of $\mathrm{tr}(Q)$ with respect to
$p_{ij}$,

$\frac{\partial{\mathrm{tr}(Q)}}{\partial{p_{ij}}}=\mathrm{tr}(Q_{i})-\frac{\mathrm{tr}(Q_{j})}{p_{ij}^{2}}=0.$
(27)

The Laplacian is strictly positive due to the positive definiteness of
$Q_{1},\ldots,Q_{k}$,

$\textstyle\nabla^{2}\mathrm{tr}(Q)=\textbf{diag}\left[\ \
\left\\{\frac{2\mathrm{tr}(Q_{j})}{p_{ij}^{3}}\right\\}_{(i,j)\in\mathcal{I}}\
\ \right]>0,$ (28)

where the pairs $(i,j)$ are ordered first by $i$ and then by $j$. Hence the
solution of (27) is a unique global minimum,

$\textstyle p_{ij}^{*}=\sqrt{\frac{\mathrm{tr}(Q_{j})}{\mathrm{tr}(Q_{i})}}.$
(29)

Substituting this choice of $p_{ij}$ into (15) completes the proof.
$\blacksquare$

The result of Lemma 4, namely (25), is a well-known result [13]. What we have
shown in Lemma 4 is that this formula explicitly requires $Q_{0}=0$ in Theorem
2. A smaller trace is achievable by introducing a nonzero $Q_{0}$ term. This
has two implications: (a) that (25) does not find the true minimum trace when
$Q_{0}$ is nonzero, and (b) that (25) is not necessarily tangent to the exact
geometric sum. If it was tangent, then the trace could not be reduced further.

Another observation, which for space we do not prove explicitly here, is that
in the first proof of Corollary 3, the coefficients $p_{ij}$ were shown to
follow (22) if the ellipsoidal bound was to be a tight outer bound. In
contrast, the Lemma 4 claims that (29) specifies the same coefficients. It can
be shown that the $n$-dimensional unit vector (which has $n-1$ degrees of
freedom) cannot be selected to reconcile the two equations for $p_{ij}$ over
all $(i,j)\in\mathcal{I}$.

##  III Application in Computing Reachable Sets

Consider the dynamics of a linear time varying (LTV) system with $r$
independent inputs,

$s_{k+1}=A_{k}s_{k}+B_{1,k}u_{1,k}+B_{2,k}u_{2,k}+\cdots+B_{r,k}u_{r,k},$ (30)

where $s_{k}\in\mathbb{R}^{n}$ represents the state and
$u_{i,k}\in\mathcal{E}({R}_{i,k})$, $R_{i,k}\in\mathbb{R}^{n\times m_{i}}$,
$i=\overline{1,r}$ are ellipsoidally bounded (independent) inputs. The
previous sections of this paper provide tools to compute the exact boundary of
the reachable states of this dynamical system and a practical outer bound. We
use the geometric sum to explore all states $s_{k}$ that are reachable through
the different realizations of $u_{i,j}$ over $j\in\overline{1,k-1}$.

To compute the reachable set, we express $s_{k}$ as a function of the prior
inputs. For simplicity, we assume the initial state $s_{1}=0$, however,
incorporating an ellipsoidally bounded set of initial conditions would be a
simple extension of this framework.

$s_{k}=\sum_{i=1}^{r}\left(\sum_{j=1}^{k-1}D_{j}B_{i,j}u_{i,j}\right),\qquad
D_{j}=\prod_{\kappa=j+1}^{k-1}A_{\kappa}.$ (31)

Equation (31) shows that the reachable set, the union of all possible state
values under any combination of admissible inputs, can be expressed as the
geometric sum of transformed, independent, and ellipsoidally bounded inputs
$u_{i,j}$.

######  Lemma 5.

[14] Given vector $x\in\mathcal{E}(Q,c)$, with shape matrix
$Q\in\mathbb{V}^{n\times n}$ and mean value $c\in\mathbb{R}^{n}$, then for any
linear mapping $T(x)=Mx$ with $A\in\mathbb{R}^{n\times n}$ the vector
$\xi=T(x)=Mx$ lies within an ellipsoid with shape matrix $MQM^{T}$ and mean
value $Mc$, i.e., $\xi\in\mathcal{E}(MQM^{T},Mc)$.

Using Lemma 5 to compute the transformed shape matrices of the input
ellipsoids, the geometric sum based on (31) that is the reachable set is given
by

$\mathcal{R}_{k}=\bigoplus_{i=1}^{r}\bigoplus_{j=1}^{k-1}\mathcal{E}\left(\Sigma_{i,j}\right),$
(32)

with $\Sigma_{i,j}=D_{j}B_{i,j}R_{i,j}B_{i,j}^{T}D_{j}^{T}$.

###  III-A Ellipsoidal Bound on the Reachable Set

The expression of the reachable set in (32) indicates that the reachable set
of the system state is a function of time, $k$, and composed of contributions
from ellipsoidally bounded inputs, which are characterized with shape
matrices, $\Sigma_{ij}$. Using the framework provided by this paper, the
reachable set is bounded by a minimum trace ellipsoid
$\mathcal{R}_{k}\subseteq\mathcal{E}(Q_{k}^{*})$, where
$\mathcal{E}(Q_{k}^{*})$ is given by Lemma 4,

$\displaystyle Q_{k,\kappa}^{*}$
$\displaystyle=\left(\sum_{i=1}^{r}\sum_{j=\kappa+1}^{k-1}\sqrt{\mathrm{tr}(\Sigma_{ij})}\right)\left(\sum_{i=1}^{r}\sum_{j=1}^{k-1}\frac{\Sigma_{ij}}{\sqrt{\mathrm{tr}(\Sigma_{ij})}}\right),$
(33)

and we omit the second subscript, $Q^{*}_{k}$, when $\kappa=0$.

It is intuitive that as the time horizon grows ($k$ becomes large), that the
stability of the system matrices $A_{k}$ is required for the reachable set and
the ellipsoidal bound to be bounded.

######  Lemma 6.

If the state matrix ($A_{k}$) is stable for all $k\in\mathbb{N}$ and inputs
$u_{i,k}$ are bounded, then the minimum trace ellipsoidal bound
$\mathcal{E}(Q_{k}^{*})$, is bounded.

Proof: Since the system is time-varying, the reachable set can potentially
change dramatically from $k$ to $k+1$. Thus we fix $k$ and show that the
sequence of historical ellipsoids $\\{Q^{*}_{k,k-\kappa}\\}$ as $\kappa$
approaches $k$ is Cauchy. As the limit of this sequence, $Q^{*}_{k}$ is then
bounded. To do this we define the scalar sequence $S_{\kappa}$

$S_{\kappa}:=\sqrt{\mathbf{tr}(Q_{k,k-\kappa}^{*})}=\sum_{i=1}^{r}\sum_{j=k-\kappa+1}^{k-1}\sqrt{\mathrm{tr}(\Sigma_{ij})}.$
(34)

Based on equation (31), for $\delta_{\kappa}=S_{\kappa+1}-S_{\kappa}$,

$\lim_{\kappa\to k}\delta_{\kappa}=\sum_{i=1}^{r}\lim_{\kappa\to
k}\sqrt{\mathrm{tr}(\Sigma_{i,k-\kappa})}=0$ (35)

and according to the ratio test,

$\lim_{\kappa\to k}\frac{\delta_{\kappa+1}}{\delta_{\kappa}}=\lim_{\kappa\to
k}\frac{\sum_{i=1}^{r}\sqrt{\mathrm{tr}(\Sigma_{i,k-\kappa-1})}}{\sum_{i=1}^{r}\sqrt{\mathrm{tr}(\Sigma_{i,k-\kappa})}}=\max_{j\in\overline{1,k}}(\rho[A_{j}])<1,$

where $\rho[.]$ denotes the maximum eigenvalue. This implies $S_{\kappa}$ is
Cauchy and convergent. Therefore, $\mathbf{tr}(Q_{\kappa}^{*})=S_{\kappa}^{2}$
is Cauchy and convergent, which concludes $Q_{k}^{*}$ is bounded.
$\blacksquare$

Figure 3: Exact boundary of geometric sum and a comparison between different
ellipsoidal bounds. Figure 4: Selection of a nonzero $Q_{0}$ reduces the trace
and produces a tangent ellipsoidal bound. Figure 5: Exact boundary of the
reachable set of a dynamical system and a comparison between different
ellipsoidal bounds.

##  IV Numerical Examples

In this section we employ the developed tools to compute the minimum trace
ellipsoidal bound over both a geometric sum and the reachable set of a
dynamical system.

Consider the geometric sum of 4 ellipsoids with dimension 2 and shape
matrices,

$\displaystyle Q_{1}$ $\displaystyle=\begin{bmatrix}[r]0.41&0.33\\\
0.33&0.31\end{bmatrix},$ $\displaystyle Q_{2}=\begin{bmatrix}[r]0.23&0.11\\\
0.11&0.06\end{bmatrix},$ $\displaystyle Q_{3}$
$\displaystyle=\begin{bmatrix}[r]0.17&-0.1\\\ -0.1&0.15\end{bmatrix},\ $
$\displaystyle Q_{4}=\begin{bmatrix}[r]0.01&0\\\ 0&0.65\end{bmatrix}.$

We apply Theorem 1 to compute for the exact boundary of the geometric sum,
plotted in blue in Fig. 3. We then compute two tight outer ellipsoidal bounds
using Corollary 3 corresponding to the standard unit vectors
$\ell_{1}=\begin{bmatrix}1&0\end{bmatrix}^{T}$ and
$\ell_{2}=\begin{bmatrix}0&1\end{bmatrix}^{T}$, producing
$\mathcal{E}(Q_{\ell_{1}})$ and $\mathcal{E}(Q_{\ell_{2}})$ (red and green,
respectively in Fig. 3),

$Q_{\ell_{1}}=\begin{bmatrix}[r]2.68&0.81\\\ 0.81&12.49\end{bmatrix},\quad
Q_{\ell_{2}}=\begin{bmatrix}[r]4.22&1.57\\\ 1.57&4.07\end{bmatrix}.$

These ellipsoids are tangent to the exact boundary of the geometric sum. Lemma
4 returns the (black) minimum trace ellipsoid, $\mathcal{E}(Q^{*})$,

$Q^{*}=\begin{bmatrix}[r]3.41&1.17\\\ 1.17&4.34\end{bmatrix}.$

As computed, $\mathcal{E}(Q^{*})$ is not tangent to the geometric sum,
however, it is visually the most representative ellipsoidal bound. We can
numerically calculate a symmetric matrix $Q_{0}$ that reduces the value of the
trace such that the resulting ellipsoidal bound becomes tangent to the exact
geometric sum. For example,

$Q_{0}=\begin{bmatrix}-0.1193&-0.0412\\\ -0.0412&-0.1521\end{bmatrix}$

satisfies the conditions of Theorem 2. The trace of $\mathcal{E}(Q^{*}+Q_{0})$
is smaller than the trace of $\mathcal{E}(Q^{*})$ and is tangent to the
geometric sum, see Fig. 4.

In the second example, consider the LTI system

$x_{k+1}=Fx_{k}+\nu_{k},\quad F=\begin{bmatrix}[r]0.67&0.35&-0.12\\\
-0.66&-0.55&0.41\\\ 2.12&1.83&0.47\end{bmatrix},$

where the noise $\nu_{k}\in\mathcal{E}(I_{3})$, is spherically bounded.

Here we compute the exact boundary of the reachable set, the minimum trace
ellipsoidal bound, and, as before, compare them with 3 different tangent
ellipsoids from Corollary 3,
$\mathcal{E}(Q_{\ell_{1}}),\mathcal{E}(Q_{\ell_{2}})$ and
$\mathcal{E}(Q_{\ell_{3}})$ constructed by the standard unit vectors. The
settling time for this system is $k^{*}=120$, therefore, the reachable set can
be closely approximated by the geometric sum of $120$ ellipsoids
$\mathcal{E}(F^{i}F^{iT})$, $i\in\overline{1,120}$. The projections of the
reachable set exact boundary and ellipsoidal bounds are shown in Fig. 5.

##  V Conclusion

In this paper we have generalized several results on characterizing the outer
ellipsoidal bound on the geometric sum of a finite number of ellipsoids.
Specifically, we introduce a symmetric matrix, $Q_{0}$, that can modify the
existing formulas for these ellipsoidal outer bounds. The presence of this
term exposes that the current formula for the minimum trace ellipsoid may not
actually touch the reachable set and, therefore, cannot be the true minimum
trace. Future work along these lines will hopefully reveal the relationship
between the choice of this $Q_{0}$ term and the input ellipsoids ($Q_{i}$) and
the choice of the coefficients ($p_{ij}$) that combine the shape matrices of
the input ellipsoids to produce the outer ellipsoidal bounds.

## References

  * [1] E. Lutwak, “The brunn-minkowski-firey theory. i. mixed volumes and the minkowski problem,” _Journal of Differential Geometry_ , vol. 38, no. 1, pp. 131–150, 1993.
  * [2] ——, “The brunn–minkowski–firey theory ii: affine and geominimal surface areas,” _Advances in Mathematics_ , vol. 118, no. 2, pp. 244–294, 1996.
  * [3] E. Behar and J.-M. Lien, “Dynamic minkowski sum of convex shapes,” in _2011 IEEE International Conference on Robotics and Automation_. IEEE, 2011, pp. 3463–3468.
  * [4] L. Guibas, L. Ramshaw, and J. Stolfi, “A kinetic framework for computational geometry,” in _24th Annual Symposium on Foundations of Computer Science (sfcs 1983)_. IEEE Computer Society, 1983, pp. 100–111.
  * [5] P. K. Agarwal, E. Flato, and D. Halperin, “Polygon decomposition for efficient construction of minkowski sums,” _Computational Geometry_ , vol. 21, no. 1-2, pp. 39–61, 2002.
  * [6] E. Fogel and D. Halperin, “Exact and efficient construction of minkowski sums of convex polyhedra with applications,” _Computer-Aided Design_ , vol. 39, no. 11, pp. 929–940, 2007.
  * [7] P. Hachenberger, “Exact minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces,” _Algorithmica_ , vol. 55, no. 2, pp. 329–345, 2009.
  * [8] E. E. Hartquist, J. Menon, K. Suresh, H. B. Voelcker, and J. Zagajac, “A computing strategy for applications involving offsets, sweeps, and minkowski operations,” _Computer-Aided Design_ , vol. 31, no. 3, pp. 175–183, 1999\.
  * [9] C. L. Bajaj and M.-S. Kim, “Generation of configuration space obstacles: The case of moving algebraic curves,” _Algorithmica_ , vol. 4, no. 1, pp. 157–172, 1989.
  * [10] A. Kaul and R. T. Farouki, “Computing minkowski sums of plane curves,” _International Journal of Computational Geometry & Applications_, vol. 5, no. 04, pp. 413–432, 1995.
  * [11] I.-K. Lee, M.-S. Kim, and G. Elber, “Polynomial/rational approximation of minkowski sum boundary curves,” _Graphical Models and Image Processing_ , vol. 60, no. 2, pp. 136–165, 1998.
  * [12] J.-R. Sack and J. Urrutia, _Handbook of computational geometry_. Elsevier, 1999.
  * [13] A. A. Kurzhanskiy and Varaiya, _Ellipsoidal calculus for estimation and control_. Nelson Thornes, 1997.
  * [14] A. A. Kurzhanskiy and P. Varaiya, “Ellipsoidal toolbox (et),” in _Decision and Control, 2006 45th IEEE Conference on_. IEEE, 2006, pp. 1498–1503.


* [63] Douglas W. Nychka and Dennis D. Cox.  Convergence rates for regularized solutions of integral equations from discrete noisy data.  The Annals of Statistics, 17:556–572, 1989.
  * [64] Sabine Pilari and Wilhelm Huisinga.  Lumping of physiologically-based pharmacokinetic models and a mechanistic derivation of classical compartmental models.  Journal of Pharmacokinetics and Pharmacodynamics, 37:365–405, 2010\.
  * [65] Abhishake Rastogi.  Tikhonov regularization with oversmoothing penalty for nonlinear statistical inverse problems.  Communications on Pure and Applied Analysis, 19(8):4111–4126, 2020\.
  * [66] Abhishake Rastogi.  Statistical inverse problems in Hilbert scales.  arXiv preprint arXiv:2208.13289, 2022.
  * [67] Abhishake Rastogi, Gilles Blanchard, and Peter Mathé.  Convergence analysis of Tikhonov regularization for non-linear statistical inverse problems.  Electronic Journal of Statistics, 14(2):2798–2841, 2020.
  * [68] Abhishake Rastogi and Peter Mathé.  Inverse learning in Hilbert scales.  Machine Learning, 112:2469–2499, 2023.
  * [69] Markus Reiß.  Asymptotic equivalence for nonparametric regression with multivariate and random design.  Annals of Statistics, 36:1957–1982, 2008.
  * [70] Saburou Saitoh and Yoshihiro Sawano.  Theory of reproducing kernels and applications.  Springer, Singapore, 2016.
  * [71] Jun Shao.  Mathematical statistics.  Springer Science & Business Media, 2003.
  * [72] Steve Smale and Ding-Xuan Zhou.  Shannon sampling II: Connections to learning theory.  Applied and Computational Harmonic Analysis, 19(3):285–302, 2005\.
  * [73] Steve Smale and Ding-Xuan Zhou.  Learning theory estimates via integral operators and their approximations.  Constructive approximation, 26(2):153–172, 2007.
  * [74] Bernhard Stankewitz.  Smoothed residual stopping for statistical inverse problems via truncated SVD estimation.  Electronic Journal of Statistics, 14:3396–3428, 2020.
  * [75] Ingo Steinwart and Andreas Christmann.  Support vector machines.  Information Science and Statistics, Springer, 2008.
  * [76] Ingo Steinwart, Don Hush, and Clint Scovel.  Optimal rates for regularized least squares regression.  In S. Dasgupta and A. Klivans, editors, Proceedings of the 22nd Annual Conference on Learning Theory, pages 79–93, 2009.
  * [77] Andrew M. Stuart.  Inverse problems: a Bayesian perspective.  Acta numerica, 19:451–559, 2010.
  * [78] Andrei N. Tikhonov.  Regularization of incorrectly posed problems.  In Soviet Mathematics Doklady, volume 4, pages 1624–1627, 1963\.
  * [79] Andrei N. Tikhonov.  Solution of incorrectly formulated problems and the regularization method.  Soviet Mathematics Doklady, 4:1035–1038, 1963.
  * [80] Tullio Valent.  Boundary value problems of finite elasticity – local theorems on existence, uniqueness, and analytic dependence on data, volume 31.  Springer Tracts in Natural Philosophy, 1987.
  * [81] Aad W. van der Vaart and Jon A. Wellner.  Weak convergence and empirical processes.  Springer Series in Statistics, Springer-Verlag, New York, 1996. With Applications to Statistics.
  * [82] Vladimir Vapnik.  Statistical learning theory, volume 1.  Wiley, New York, 1998.
  * [83] Grace Wahba.  Practical approximate solutions to linear operator equations when the data are noisy.  SIAM journal on numerical analysis, 14(4):651–667, 1977.
  * [84] Frederic Weidling, Benjamin Sprung, and Thorsten Hohage.  Optimal convergence rates for Tikhonov regularization in besov spaces.  SIAM Journal on Numerical Analysis, 58(1):21–47, 2020.
  * [85] Frank Werner and Bernd Hofmann.  Convergence analysis of (statistical) inverse problems under conditional stability estimates.  Inverse Problems, 36(1):015004, 2019.
  * [86] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.  On early stopping in gradient descent learning.  Constructive Approximation, 26:289–315, 2007.