# Measuring vagueness and subjectivity in texts: from symbolic to neural VAGO

Benjamin Icard1, Vincent Claveau2, Ghislain Atemezing3 and Paul Égré1
1Institut Jean-Nicod (CNRS, ENS-PSL, EHESS), Paris, France  2IRISA-CNRS,
Rennes, France & Direction Générale de l’Armement, Bruz, France  3Mondeca,
Paris, France

###### Abstract

We present a hybrid approach to the automated measurement of vagueness and
subjectivity in texts. We first introduce the expert system VAGO, we
illustrate it on a small benchmark of fact vs. opinion sentences, and then
test it on the larger French press corpus FreSaDa to confirm the higher
prevalence of subjective markers in satirical vs. regular texts. We then build
a neural clone of VAGO, based on a BERT-like architecture, trained on the
symbolic VAGO scores obtained on FreSaDa. Using explainability tools (LIME),
we show the interest of this neural version for the enrichment of the lexicons
of the symbolic version, and for the production of versions in other
languages.

###### Index Terms:

Vagueness, Subjectivity, Precision, Detail, Hybridization, Explainability,
Multidimensionality

##  I Introduction

How do we decide whether a statement is factual or whether it reports a mere
opinion when we lack access to first-hand knowledge? This question is of
central importance in order to assess and enhance information quality on the
web and in other media.

In 2018, PEW Research Center (henceforth PRC) conducted a survey among North-
Americans, intended to test the public’s ability to recognize statements
either as expressing mere opinion or as reporting facts in the news. While
each statement in their sample was correctly classified by a majority of
participants, only 26% were able to correctly identify all factual statements
as such in the test sample, and only 35% to categorize all opinion statements
as opinion [21]. Despite asking participants to issue judgments “regardless of
[their] knowledge of the topic”, PRC did not give an account of the linguistic
cues that a competent language-user ought to rationally identify as conveying
objective or subjective information. As argued by Kaiser and Wang in [14],
however, whether a statement is fact-like or opinion-like depends on
“linguistic packaging”.

In order to clarify this issue, this paper presents a symbolic tool called
VAGO, designed to assess informational quality in textual documents, by
providing measures of vagueness vs. precision in discourse [26, 7], but also
of subjectivity vs. objectivity [15]. So far, automatic vagueness detection
has been considered in the context of privacy policies, for scoring vagueness
at the level of words and sentences [4], for predicting whether a word is
vague or not based on the vector representation of vague expressions in
recurrent neural networks [19], or for generating different degrees of vague
sentences using adversarial networks [17], with results further exploited in
[18] to evaluate the support of individual sentences to the vagueness
prediction of whole documents. Concerning the detection of opinion, measures
of subjectivity have been considered at the level of sentences and documents
[1]. Following [25], [9] observed that in French articles, some syntactic
markers (e.g. exclamation, interrogation and suspension points) are
significantly more prevalent in opinion articles than in factual articles, as
for semicolon and colon. Conversely, like [16] for English newspapers, [9]
also observed that factual articles in French contained more named entities
(e.g. dates, values, percentage) than opinion articles.

Our own approach relies on the observation that a subclass of vague
expressions, comprised in particular of multi-dimensional vague adjectives,
constitutes a reliable marker of subjectivity [23, 14], and therefore of
opinion. To leverage it, we combine two distinct methods. On the one hand, we
use an expert system called VAGO [10, 11, 12], which relies on symbolic rules
for detecting and measuring lexical vagueness and subjectivity in textual
documents. On the other hand, we create a neural counterpart of symbolic VAGO,
called VAGO-N, in order to test and enhance the expert system’s performance.
One of the goals of this method is to extend the results of the expert system
to languages other than French and English. But we also present the potential
use of VAGO-N, initially trained for predicting scores through regression, for
detecting false information, or fake news.

##  II The Symbolic Tool VAGO

###  II-A Typology of vagueness and measures of detail

VAGO measures vagueness and subjectivity in textual documents based on a
lexical database for French and English [3], with rules for vagueness scoring
and vagueness cancellation depending on the syntactic context (see below).
Built on a typology derived from [8], this database provides an inventory of
vague terms in four categories: approximation vagueness ($V_{A}$), generality
vagueness ($V_{G}$), degree vagueness ($V_{D}$), and combinatorial vagueness
($V_{C}$).

Approximation vagueness primarily concerns modifiers like “environ”
(“approximately”), which relax the truth conditions of the modified
expression. Generality vagueness includes determiners like “certains”
(“certain”) and modifiers like “au plus” (“at most”). Unlike expressions of
approximation, the latter have precise truth conditions. The category of
expressions related to degree vagueness and combinatorial vagueness [2] mainly
consists of one-dimensional gradable adjectives (such as “grand” - “big”,
“vieux” - “old”) and multidimensional gradable adjectives (like “beau” -
“beautiful”, “intelligent” - “intelligent”, “bon” - “good”, “qualifié” -
“qualified”). Expressions of type $V_{A}$ and $V_{G}$ are treated as factual,
while expressions of type $V_{D}$ and $V_{C}$ are treated as subjective [15,
27, 23].

In the original version of VAGO [11], a sentence is considered to be vague if
it contains at least one marker of vagueness, and subjective if it contains at
least one marker of subjectivity. However, the precision of sentences and
texts is evaluated only _negatively_ : a sentence is precise exactly if it
does not contain any vague markers. As an example, VAGO would assign identical
vagueness and subjectivity scores of 1 to the following two sentences, because
both contain at least one marker of vagueness/subjectivity (“important” in
(a), “quickly” and “excellent” in (b)):111Sentence (a) is an English
translation of a sentence taken from the Wikipedia article on Joseph
Bonaparte, while sentence (b) is inspired by a false news or “fake news”
story.

.[(a)] King of Naples from 1806 to 1808, then of Spain from 1808 to 1813, he
is an important figure in the plan implemented by Napoleon to establish the
sovereignty of France over continental Europe.

.[(b)] To quickly cure Covid-19, one must take an excellent herbal decoction.

Intuitively, however, sentence (a), which contains nine named entities
(underlined terms in the sentence), is more informative than sentence (b),
which only contains one named entity (“Covid-19”), and therefore provides
fewer details than (a). To address this limitation, here the current version
of VAGO is enriched with a relative detail score, based on the proportion of
named entities compared to vague expressions.

###  II-B Scores: Vagueness, Subjectivity, Detail

The current version of VAGO is able to measure the scores of vagueness,
subjectivity, but also of detail in English and French documents. The
detection of vagueness and subjectivity relies on a lexical database, which
consisted of 1,640 terms in both languages at the time of the experiments [3],
distributed as follows by vagueness category: $|V_{A}|$ = 9, $|V_{G}|$ = 18,
$|V_{D}|$ = 43, and $|V_{C}|$ = 1570. Regarding the level of detail, the
detection is based on identifying named entities (such as people, locations,
temporal indications, institutions, and numbers) using the open-source library
for Natural Language Processing spaCy.222https://spacy.io/

For a given sentence $\phi$, its vagueness score is defined as the ratio
between the number of vague words in $\phi$ and the total number of words in
the sentence, written $N_{\phi}$:

$\displaystyle
R_{vagueness}(\phi)=\frac{\overbrace{|V_{D}|_{\phi}+|V_{C}|_{\phi}}^{\text{subjective}}+\overbrace{|V_{A}|_{\phi}+|V_{G}|_{\phi}}^{\text{factual}}}{N_{\phi}}$
(1)

where $|V_{A}|{\phi}$, $|V_{G}|{\phi}$, $|V_{D}|{\phi}$, and $|V_{C}|{\phi}$
represent the number of terms in $\phi$ belonging to each of the four
vagueness categories (approximation, generality, degree vagueness, and
combinatorial vagueness). More specifically, the subjectivity score of a
sentence $\phi$ is calculated as the ratio between the subjective vague
expressions in $\phi$ and the total number of words in $\phi$. Similarly, a
factual vagueness score can be calculated with the expressions of generality
and approximation (see sections III and IV):

$\displaystyle R_{subjectivity}(\phi)$
$\displaystyle=\frac{|V_{D}|_{\phi}+|V_{C}|_{\phi}}{N_{\phi}}$ (2)
$\displaystyle R_{factual~{}vagueness}(\phi)$
$\displaystyle=\frac{|V_{A}|_{\phi}+|V_{G}|_{\phi}}{N_{\phi}}$ (3)

The detail score of a sentence can be defined as the ratio
$R_{detail}(\phi)=\frac{|P|_{\phi}}{N_{\phi}}$, where $|P|_{\phi}$ denotes the
number of named entities in the sentence (referential terms). By extension, if
$|V|_{\phi}$ denotes the number of vague terms in a sentence (across all
categories), we define the detail/vagueness score of a sentence as the
relative proportion of named entities, given by:

$\displaystyle R_{detail/vagueness}(\phi)$
$\displaystyle=\frac{|P|_{\phi}}{|P|_{\phi}+|V|_{\phi}}$ (4)

In the previous example, we can verify that $R_{detail/vagueness}($a$)=9/10$,
while $R_{detail/vagueness}($b$)=1/3$, indicating a higher measure of
informativeness for (a).

For a text $T$ (set of sentences), the vagueness scores (including subjective
vagueness and factual vagueness) are defined as the proportion of sentences of
$T$ whose vagueness score (subjective or factual) is non-zero. The
detail/vagueness score of a text $T$ is defined as the average of the
$R_{detail/vagueness}$ ratios for each sentence in $T$.

The online version of VAGO, available on the Mondeca
website,333https://research.mondeca.com/demo/vago/. See [11, 12] for the
implementation details. showcases the functionalities of the original version
of VAGO. The website offers a graphical interface to measure the vagueness and
subjectivity scores of texts using two barometers. The first barometer
represents the degree of vagueness in a text (defined as $R_{vagueness}(T)$),
while the second barometer indicates the extent to which the text expresses an
opinion rather than a fact, in other words, the proportion of subjective
vocabulary within the text (defined as $R_{subjectivity}(T)$).

###  II-C English VAGO on factual versus opinion statements

In [10], VAGO was applied to a large set of more than 28,000 documents from
four different corpora. A positive correlation was found between the
classification of texts as biased by a CNN based classifier and the vagueness
scores computed by VAGO. In this section, we provide a more analytic
perspective by showing the predictions of VAGO on the test set used by PRC to
evaluate lay people’s judgments of fact vs. opinion. Although the set is very
limited (10 sentences), it provides a useful benchmark for comparison, in
particular because PRC tested the statements on a large sample of participants
($N=5,035$).

Figure 1 presents PRC’s 10 test sentences, comprised of 5 statements labelled
as “opinion” and 5 statements labelled as “factual” (based on PRC’s
prescriptive classification). The participants recruited by PRC were
instructed that a statement should be considered as “factual” in case it can
“be proved or disproved based on _objective evidence_ ” (our emphasis), and
_regardless of “whether you think it is accurate or not”_. By contrast, a
statement counted as an “opinion” if “they thought that it was based on the
_values and beliefs_ of the journalist or the source making the statement, and
could not definitively be proved or disproved based on objective evidence”,
and _regardless of “whether you agree with it or not”_[21] (our emphasis).

1. _ISIS lost a significant portion of its territory in Iraq and Syria in 2017._ [F/O] 2. _Immigrants who are in the U.S. illegally have some rights under the Constitution._ [F/F] 3. _Health care costs per person in the U.S. are the highest in the developed world._ [F/O] 4. _Spending on Social Security, Medicare, and Medicaid make up the largest portion of the U.S. federal budget._ [F/O] 5. _President Barack Obama was born in the United States._ [F/F] 6. _Democracy is the greatest form of government._ [O/O] 7. _Government is almost always wasteful and inefficient._ [O/O] 8. _Increasing the federal minimum wage to $15 an hour is essential for the health of the U.S. economy._ [O/O] 9. _Immigrants who are in the U.S. illegally are a very big problem for the country today._ [O/O] 10. _Abortion should be legal in most cases._ [O/O]

Figure 1: PRC’s sentences, grouped by category (F=fact; O=opinion). Within
brackets: PRC’s classification (left) vs. VAGO’s (right). In blue: cases in
which VAGO differs. Boldfaced expressions: VAGO entries detected.

While the proportion of fact vs. opinion answers varied depending on the
sentence, for each statement the majority of participants agreed with the
classification made by PRC (mode ranging from 54% to 77% for factual
statements, and between 68% and 80% for opinion statements), giving support to
the PRC labels.

Because participants were asked to decide whether a statement is factual or
opinion regardless of world knowledge and personal beliefs, this justifies
looking at the linguistic cues they should be aware of to solve the task. The
category ascribed by VAGO to each particular statement is reported in Figure 1
(right label). The statements for which VAGO’s classification differs from the
PRC classification are highlighted in blue. In Figure 2 are displayed the
results of VAGO’s classification for statement 4, “ _Government is almost
always wasteful and inefficient_ ”. Note that for a single sentence, the
barometers necessarily take categorical values, intermediate values are only
obtained over larger texts.

Figure 2: VAGO’s results for the sentence “ _Government is almost always
wasteful and inefficient_ ”. VAGO scores are binarized for sentences, but
yield intermediate values for larger texts.

As shown in Figure 1, VAGO classifies eight statements as opinion, and only
two as factual. More specifically, the two sentences classified as factual by
VAGO (2 and 5) are indeed factual according to the PRC’s criterion.
Conversely, the five sentences labelled “opinion” by PRC (6-10) are classified
as opinions by VAGO. This means VAGO uses a stricter criterion on what to
count as factual, and a laxer one on what to count as opinion relative to this
sample.

According to VAGO, sentences 1, 3, 4, 6-10, are all opinion statements since
they contain at least one marker of subjectivity (see Figure 1). But, as with
the sentences (a) and (b) given above, some of those statements are more
informative than others since they contain more named entities. The measure of
detail/vagueness we introduced in subsection II-B helps distinguish those
sentences in terms of informativity. For instance, although sentences 4 and 9
both receive a score of subjectivity equal to 1, $R_{detail/vagueness}(4)=4/5$
while $R_{detail/vagueness}(9)=1/3$.

More specifically, four of the five statements marked as opinion by PRC are
identified as such by VAGO based on the occurrence of an expression of type
$V_{C}$ (“great”, “wasteful”, “inefficient”, “essential”, “big”) as well as
$V_{D}$ (“very”). Our hypothesis is that participants relied on those items to
decide that the statements convey subjective values or beliefs.

Looking more specifically at the statements for which the classifications
diverge, we can see that in statements 3 and 4, VAGO classifies the
superlatives “highest” and “largest” as elements of the category $V_{D}$.
While VAGO has rules of vagueness cancellation for comparatives in the
category $V_{D}$ (“taller”) and for measure phrases (“5 feet tall”), it does
not cancel vagueness in superlatives currently. For “greatest” in 6, this is
as it should be, since even the superlative leaves room for subjective
disagreement, but for “highest” and “largest”, the interpretation seems
objective and factual. In the case of 1, “significant” is the pivotal element
behind VAGO’s classification of the sentence as opinion. We note that 30% of
participants rated the sentence as opinion, possibly relying on the fact that
what counts as “significant” is a matter of interpersonal disagreement.
Finally, for sentences 2 and 5 classified as fact by VAGO and by PRC alike, 5
is the only sentence categorized as precise by VAGO, 2 is vague but “some” is
$V_{G}$ and not counted as a marker of subjectivity.

###  II-D French VAGO on regular versus satirical press articles

To scale up analytic intuitions, VAGO was tested on the French corpus
“FreSaDa”444https://github.com/adrianchifu/FreSaDa [13], consisting of 11,570
press articles divided into two supposed homogeneous classes: 5,648 “regular”
articles from the general French press, not presumed to be false, versus 5,922
“satirical” articles explicitly including false or made up content. Within the
total corpus, VAGO processed 10,969 out of the initial 11,570 articles, with
the remaining 601 articles excluded due to inappropriate format for analysis
(isolated words, keywords, incomplete sentences, etc.). The results provided
by VAGO are reported in Figure 3.

Figure 3: Average ratio scores per article of the FreSaDa corpus (French)
according to VAGO.

According to VAGO, the articles in the satirical corpus are significantly
_more vague_ ($p=4.99\times 10^{-11}$), _more subjective_ ($p=1.69\times
10^{-9}$), and _less detailed_ ($p=3.36\times 10^{-22}$) than the articles in
the regular press corpus (scores calculated per text; two-tailed t-tests,
$\alpha=0.05$, with Bonferroni correction). These results align with
expectations and support the findings previously obtained with VAGO on English
texts [10].

To further exemplify the interest of these ratios, we conducted a simple
classification experiment: the goal was to distinguish between the two types
of documents in the FreSaDa corpus solely based on the vagueness, subjectivity
and detail/vagueness scores. For a given text of the corpus, the ratios of
each of its sentences were obtained with VAGO; the minimum, median, average
and maximum of each ratio on all the sentences were computed and used as input
to an XGBoost classifier [5] (300 rounds, max_depth=8). The accuracy obtained
with different sizes of the training set showed that the ratios scores are
effective cues to classify such documents as being either regular or
satirical. Moreover, very few examples were necessary to yield high accuracy,
the plateau being reached at 500 documents.

##  III The neural version VAGO-N

###  III-A Training of the VAGO clone

We built a neural version of the symbolic VAGO called VAGO-N, based on
combining a BERT [6] architecture with a regression layer and an MSE loss
function to predict a score of vagueness for sentences. In the present
experiment, we tested both subjective and factual vagueness, but for the sake
of completeness, we also tested the prediction of the $R_{detail/vaguenesss}$
score. However, since this score can be more simply computed from a named
entity recognition system, we did not return to it in those experiments. As in
a distillation task, VAGO was used to associate a vagueness score to each
sentence in the FreSaDa corpus and thus to train a neural system.

In the experiments reported in the following sections, 106,000 sentences out
of 141,137 were randomly selected within the 10,969 articles of the FreSaDa
corpus processed by VAGO, and divided into a training set (85,000 sentences)
and a test set (21,000 sentences). We used a RoBERTa Large model (Batch
Size=30; Learning Rate=1e-6; Epochs=20); experiments not detailed here with a
CamemBERT model [20] provided slightly lower results.

Performance is reported in Table I with standard regression measures: root-
mean-square error (RMSE), coefficient of determination ($R^{2}$), mean
absolute error (MAE) and median absolute error (MedAE). All these measures
show that VAGO-N replicates the symbolic VAGO scores with high accuracy. The
task of detecting subjectivity seems a little more difficult than in the case
of factual vagueness detection.

| RMSE | $R^{2}$ | MAE | MedAE
---|---|---|---|---
subjective vagueness | 0.022063 | 0.859897 | 0.014518 | 0.009488
factual vagueness | 0.008745 | 0.949339 | 0.004124 | 0.001730
detail/vague | 0.097008 | 0.882543 | 0.051396 | 0.012367
TABLE I:  Regression results of VAGO-N for scores of subjective vagueness,
factual vagueness and detail/vagueness concerning the sentences of the FreSaDa
corpus (French).

###  III-B Comparison of the versions of VAGO

The previous quantitative evaluation indicates that VAGO-N replicates the
general behavior of VAGO quite faithfully. From a qualitative perspective, we
aim to verify here that this neural version relies on the same lexical cues as
the symbolic version. For this purpose, we use the explainability tool LIME
[22]. Applied to the outputs of VAGO-N, LIME identifies the tokens that
contribute the most (or the least) to the vagueness score of a given text. In
Figure 4, we provide an example of LIME output on a French sentence for
subjective vagueness. Using this tool, we examine the cases where the
predictions of vagueness scores by VAGO-N diverge the most from those of VAGO.

Figure 4: Example of a LIME output on a French sentence from the FreSaDa
corpus processed by VAGO-N. The category labeled as “neutre” corresponds to
the inverse category of vagueness, contributing negatively to the vagueness
score.

The study of these error cases puts emphasis on several aspects. Regarding the
differences between VAGO and VAGO-N for the prediction of factual vagueness,
the vast majority of terms identified as contributing the most to the
prediction of VAGO-N are already present in the French lexicon of VAGO, both
in case of generality vagueness (e.g., _“tout/tous/toutes”, “jamais”, “ou”,
“général”, “quelques”, “certains/certaines”_), and in case of approximation
vagueness (_“environ”, “presque”_). Those indicators of factual vagueness are
correct, but their weight in the final score of VAGO-N differs from the
calculation performed by the original VAGO, which does not put any weight on
lexical items. This difference in weight may result from words of morpho-
syntactic categories not considered by VAGO, which may amplify or diminish the
resulting factual vagueness score, according to the neural network.

Similarly, in the case of subjective vagueness, LIME applied to VAGO-N
identifies adjectives and terms of excess that were already present in the
extant VAGO lexicon, either within the category of combinatorial vagueness
(e.g., _“négatif”, “affirmatif”, “intéressant”, “fortement”, “chiant”,
“difficile”, “probablement”, “vrai”, “stupide”, “vraiment”_), or within the
category of degree vagueness (_“petit”_). But LIME also identifies other
adjectives carrying combinatorial vagueness that are not yet in the lexicon
and should be included (e.g., _“durable”, “particulièrement”, “ringard”,
“actuel”_), with some exceptions (“ _sabbatique_ ”).

##  IV Extensions of the VAGO Approaches

###  IV-A Validation and enrichment of the symbolic VAGO

For each token $t$ in a text, LIME provides a score for the contribution of
$t$ to the vagueness prediction (subjective or factual) in the text, which we
denote $c_{occ}(t)$. In the case of a sentence, the higher the $c_{occ}(t)$ of
a term $t$ occurring in the sentence, the more positively $t$ contributes to
the vagueness score of that sentence.

By applying LIME to the 141,137 sentences of the FreSaDa corpus processed by
VAGO and exploited in VAGO-N, we collected the contribution scores $c_{occ}$
of all occurrences of all the tokens within these sentences. To obtain a
global score $c_{tok}(t)$ per token $t$, we summed and normalized the
$c_{occ}$ by the total number of occurrences of each token noted here
$|occ_{t}|$: $c_{tok}(t)=\frac{1}{|occ_{t}|}\sum_{o\in occ_{t}}c_{occ}(o)$.
Our hypothesis was that terms from the VAGO lexicon should be prioritized
among tokens receiving the highest $c_{tok}$. To test it, we calculated the
statistical precision (proportion of VAGO instances retrieved) on the list of
tokens ordered by decreasing $c_{tok}$. Note that a token is taken into
account if it is an inflection of a term in the VAGO lexicon. The results are
listed in Table II, where P@$k$ represents the precision over the first $k$
tokens in the list.

Figure 5 shows the ROC curve relating the $c_{tok}$ score to presence in the
French VAGO lexicon. These results support our hypothesis. Although VAGO-N has
been only trained on sentences and their scores, it is able to reconstruct the
lexicon at the core of the symbolic version.

vagueness type | P@5 | P@10 | P@20 | P@30 | P@100 | P@200
---|---|---|---|---|---|---
subjective | 1.00 | 1.00 | 0.95 | 0.93 | 0.81 | 0.79
factual | 1.00 | 1.00 | 1.00 | 0.93 | 0.31 | 0.16
TABLE II: Comparison of the precision at different thresholds for the French
tokens of the VAGO lexicon ordered by $c_{tok}$. Figure 5:  ROC curve of
$c_{tok}$ as an indicator of its presence in the French lexicon of VAGO.

Besides, we examined the 100 tokens with the highest $c_{tok}$ for subjective
vagueness: in addition to the 81 well present in the lexicon, a few verbal
forms are listed. Although considered false positives (current VAGO lexicons
only list adjectives and adverbs), their relevance can be debated. In the
remaining tokens, seven absent words were validated as relevant and worthy of
inclusion in the lexicons. This list contains four adverbs (_“également”,
“seulement”, “particulièrement”, “clairement”_) for which the VAGO database
contains the root adjectives in two cases (_“particulier”, “clair”_), an
action verb (_“faire”_), an adjective that can also be a noun
(_“droit/droite”_), and a noun (_“nombre”_). We also noted the detection of
non-standard forms of terms present in the lexicon (_“difficille”_ ,
_“pauv”_), illustrating the robustness of the neural approach on noisy text
(typo, abbreviation, etc.). The results validate the neural clone VAGO-N,
which retrieves the lexical cues of the expert system VAGO, while identifying
new or non-standard forms.

###  IV-B Developing multilingual versions of VAGO-N

Developing symbolic versions of VAGO for other languages requires vague
lexicons to be available in the target languages. However, automatic
translation of these lexicons is not possible due to the idiomatic and out-of-
context nature of the lists of expression involved.

That being said, it is possible to translate the VAGO-N training set by
relying on the following assumption: vagueness scores, in particular
subjective vagueness and factual vagueness scores, are preserved from the
source language into the target language. To begin with, the FreSaDa corpus
was translated from French into English using the Helsinki-NLP/opus-mt-fr-
en555https://huggingface.co/Helsinki-NLP/opus-mt-fr-en model [24]. Next,
VAGO-N was trained to predict subjective vagueness and factual vagueness
scores on this English corpus (using the same hyper-parameters as for training
VAGO-N on French). The regression results are similar to those obtained for
French, and presented in Table III.

vagueness type | RMSE | $R^{2}$ | MAE | MedAE
---|---|---|---|---
subjective | 0.031801 | 0.708915 | 0.022865 | 0.016807
factual | 0.016990 | 0.808772 | 0.009582 | 0.004172
TABLE III:  Regression results of VAGO-N for scores of subjective and factual
vagueness concerning the English version of the FreSaDa sentences.

Applying the same approach as in subsection IV-A, we isolated the list of
tokens ordered by decreasing $c_{tok}$, then compared it to the English
lexicon of VAGO, which serves as ground-truth. The accuracy of this list
measured at different thresholds is reported in Table IV. The corresponding
ROC curves are presented in Figure 6.

vagueness type | P@5 | P@10 | P@20 | P@30 | P@100 | P@200
---|---|---|---|---|---|---
subjective | 0.80 | 0.90 | 0.90 | 0.93 | 0.90 | 0.84
factual | 1.00 | 0.80 | 0.55 | 0.50 | 0.26 | 0.14
TABLE IV:  Comparison of the precision at different thresholds for the list of
English tokens ordered by $c_{tok}$ as a function of the VAGO lexicon. Figure
6: ROC curve of $c_{tok}$ as an indicator of its presence in the English
lexicon of VAGO.

We also collected the 100 most vagueness-prone English terms according to
VAGO-N. These terms were compared with those in the extant English lexicon of
the symbolic version: 90 terms were already included in the VAGO English
lexicon. Among the highest-ranking terms from the top 100 that do not appear
in VAGO, we found five adjectives or adverbs that could appear in the
combinatorial vagueness category (_“likely”, “full”, “complicated”, “frankly”,
“enough”_), one modal verb (“ _must”_), which it also makes sense to include
given the presence of _“should”_ in the VAGO lexicon. Four terms, on the other
hand, are not clearly vague (_“course”, “lost”, “lose” and “finally”_), with
the possible exception of “course” (occurrences in “of course”, the use of
which is subjective). Of the next 100 terms, all those not included in the
VAGO lexicon are adjectives that can be included in the $V_{C}$ category
(_“worse”, “complex”_ , etc.).

##  V Conclusion

In this article, we first presented VAGO, a struculexicon and rule-based
system which calculates scores of vagueness, subjectivity, and
detail/vagueness for texts. We then created a neural clone, VAGO-N, based on
BERT. Unlike VAGO, VAGO-N is trained solely on VAGO scores, without knowledge
of the lexicon underlying this symbolic version. Using LIME, the terms with
the highest contribution to VAGO-N scores turn out to be either terms that
already appear in VAGO, or terms mostly susceptible to appear in it. This
suggests that the decisions of VAGO-N are largely explained by lexical items
identified by the symbolic VAGO. Once trained, VAGO-N can be used to complete
the extant lexicons of the symbolic VAGO. But it can also be used to produce
neural versions of VAGO in other languages and to generate lexicons for
symbolic versions in these languages.

More work remains to be done. We plan to measure the genericity of our
approach by masking the named entities in a text to see whether the VAGO-N
scores remain stable before and after this operation, in order to determine
the proportion of the VAGO lexicon (which does not contain named entities)
actually influencing the decision of VAGO-N.

On a more applied level, we are now extending VAGO with additional markers of
subjectivity besides adjectives, in particular with explicit markers (first-
person pronouns, exclamation marks), but also with more contextual features
(direct vs. reported discourse). Ultimately, our goal is to update its
interface to help users have a reliable grasp of levels of objectivity and
subjectivity in the texts they read in the media.

## Acknowledgements

We thank four anonymous reviewers for helpful comments and several colleagues
for feedback. This work was carried out with the support of the programs
HYBRINFOX (ANR-21-ASIA-0003), FRONTCOG (ANR-17-EURE-0017 program), and PLEXUS
(Marie Skłodowska-Curie Action, Horizon Europe Research and Innovation
Programme, grant agreement n°101086295).

## References

  * [1] T. Alhindi, S. Muresan, and D. Preoţiuc-Pietro.  Fact vs. opinion: the role of argumentation features in news classification.  In Proceedings of the 28th international conference on computational linguistics, pages 6139–6149, 2020.
  * [2] W. P. Alston.  Philosophy of Language.  Prentice Hall, 1964.
  * [3] G. Atemezing, B. Icard, and P. Égré.  Vague Terms in SKOS to detect vagueness in textual documents, June 2022\.
  * [4] J. Bhatia, T. D. Breaux, J. R. Reidenberg, and T. B. Norton.  A theory of vagueness and privacy risk perception.  In 2016 IEEE 24th International Requirements Engineering Conference (RE), pages 26–35. IEEE, 2016.
  * [5] T. Chen and C. Guestrin.  XGBoost: A scalable tree boosting system.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 785–794, New York, NY, USA, 2016. ACM.
  * [6] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  arXiv:1810.04805 [cs], Oct. 2018.
  * [7] P. Égré.  Qu’est-ce que le vague? Vrin, 2018.
  * [8] P. Égré and B. Icard.  Lying and vagueness.  In J. Meibauer, editor, Oxford Handbook of Lying. OUP, 2018.
  * [9] L. Escouflaire.  Identification des indicateurs linguistiques de la subjectivité les plus efficaces pour la classification d’articles de presse en français.  In Actes de la 29e Conférence sur le Traitement Automatique des Langues Naturelles, pages 69–82, 2022.
  * [10] P. Guélorget, B. Icard, G. Gadek, S. Gahbiche, S. Gatepaille, G. Atemezing, and P. Égré.  Combining vagueness detection with deep learning to identify fake news.  In IEEE 24th International Conference on Information Fusion (FUSION), pages 1–8, 2021.
  * [11] B. Icard, G. Atemezing, and P. Égré.  VAGO: un outil en ligne de mesure du vague et de la subjectivité.  In Conférence Nationale sur les Applications Pratiques de l’Intelligence Artificielle (PFIA 2022), pages 68–71, 2022.
  * [12] B. Icard, V. Claveau, G. Atemezing, and P. Égré.  Un traitement hybride du vague textuel: du système expert VAGO à son clone neuronal.  In Conférence sur le Traitement Automatique des Langues Naturelles (TALN 2023), 2023.
  * [13] R.-T. Ionescu and A.-G. Chifu.  FreSaDa: A French satire data set for cross-domain satire detection.  In The International Joint Conference on Neural Network, IJCNN 2021, IJCNN2021, 2021.
  * [14] E. Kaiser and C. Wang.  Packaging information as fact versus opinion: Consequences of the (information-)struc-
tural position of subjective adjectives.  Discourse Processes, 58(7):617–641,
2021.

  * [15] C. Kennedy.  Two sources of subjectivity: Qualitative assessment and dimensional uncertainty.  Inquiry, 56(2-3):258–277, 2013.
  * [16] K. R. Krüger, A. Lukowiak, J. Sonntag, S. Warzecha, and M. Stede.  Classifying news versus opinions in newspapers: Linguistic features for domain independence.  Natural Language Engineering, 23(5):687–707, 2017.
  * [17] L. Lebanoff and F. Liu.  Automatic detection of vague words and sentences in privacy policies.  arXiv preprint arXiv:1808.06219, 2018.
  * [18] X. Lian, D. Huang, X. Li, Z. Zhao, Z. Fan, and M. Li.  Really vague? Automatically identify the potential false vagueness within the context of documents.  Mathematics, 11(10):2334, 2023.
  * [19] F. Liu, N. L. Fella, and K. Liao.  Modeling language vagueness in privacy policies using deep neural networks.  In 2016 AAAI Fall Symposium Series, 2016.
  * [20] L. Martin, B. Muller, P. J. O. Suárez, Y. Dupont, L. Romary, É. V. de La Clergerie, D. Seddah, and B. Sagot.  CamemBERT: a tasty French language model.  arXiv preprint arXiv:1911.03894, 2019.
  * [21] A. Mitchell, J. Gottfried, M. Barthel, and N. Sumida.  Distinguishing between factual and opinion statements in the news.  Pew Research Center, 2018.
  * [22] M. T. Ribeiro, S. Singh, and C. Guestrin.  “Why Should I Trust You?”: Explaining the Predictions of Any Classifier.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, page 1135–1144, New York, NY, USA, 2016. Association for Computing Machinery.
  * [23] S. Solt.  Multidimensionality, subjectivity and scales: Experimental evidence.  In E. Castroviejo, L. McNally, and G. Sassoon, editors, The Semantics of Gradability, Vagueness, and Scale Structure, pages 59–91. Springer, 2018.
  * [24] J. Tiedemann and S. Thottingal.  OPUS-MT — Building open translation services for the World.  In Proceedings of the 22nd Annual Conferenec of the European Association for Machine Translation (EAMT), Portugal, 2020.
  * [25] A. Todirascu.  Genre et classification automatique en TAL: le cas de genres journalistiques.  Linx. Revue des linguistes de l’université Paris X Nanterre, (78), 2019.
  * [26] K. Van Deemter.  Not exactly: In praise of vagueness.  OUP Oxford, 2010.
  * [27] S. Verheyen, S. Dewil, and P. Égré.  Subjectivity in gradable adjectives: The case of tall and heavy.  Mind & Language, 33(5):460–479, 2018.


# Fast Low Rank column-wise Sensing: short proof

Namrata Vaswani
Iowa State University, Ames, IA, USA.
Email<EMAIL_ADDRESS>
# A Simple Proof for Fast and Sample-Efficient Federated Low Rank Matrix
Recovery from column-wise Linear Projections

Namrata Vaswani
Iowa State University, Ames, IA, USA.
Email<EMAIL_ADDRESS>
# A Simple Proof for
Efficient Federated Low Rank Matrix Recovery from column-wise Linear
Projections

Namrata Vaswani
Iowa State University, Ames, IA, USA.
Email<EMAIL_ADDRESS>
###### Abstract

This note provides a significantly simpler and shorter proof of our sample
complexity guarantee for solving the low rank column-wise compressive sensing
(LRCS) problem using the Alternating Gradient Descent (GD) and Minimization
(AltGDmin) algorithm. AltGDmin was developed and analyzed for solving LRCS in
our recent work. We also provide an improved guarantee.

##  I Introduction

We study the low rank column-wise compressive sensing (LRCS) problem which
involves recovering a low rank (LR) matrix from independent compressive
measurements of each of its columns. The alternating gradient descent (GD) and
minimization (altGDmin) algorithm for solving it in a fast,
memory/communication-efficient and private fashion was developed and analyzed
in our recent work [1]. This brief note provides a significantly simpler and
shorter proof of our sample complexity guarantee for AltGDmin. In fact, it
also improves our guarantee for the altGDmin iterations.

##  II Problem statement, notation, and algorithm

###  II-A Problem statement and assumption

The goal is to recover an $n\times q$ rank-$r$ matrix
${\bm{X}}^{\star}{}=[\bm{x}^{\star}_{1},\bm{x}^{\star}_{2},\dots,\bm{x}^{\star}_{q}]$
from $m$ linear projections (sketches) of each of its $q$ columns, i.e. from

$\displaystyle\bm{y}_{k}:=\bm{A}_{k}\bm{x}^{\star}_{k},\ k\in[q]$ (1)

where each $\bm{y}_{k}$ is an $m$-length vector, $[q]:=\\{1,2,\dots,q\\}$, and
the measurement/sketching matrices $\bm{A}_{k}$ are mutually independent and
known. The setting of interest is low-rank (LR), $r\ll\min(n,q)$, and
undersampled measurements, $m<n$. Our guarantees assume that each $\bm{A}_{k}$
is random-Gaussian: each entry of it is independent and identically
distributed (i.i.d.) standard Gaussian. Let
${\bm{X}}^{\star}{}\overset{\mathrm{SVD}}{=}{\bm{U}}^{\star}{}{\bm{\Sigma}^{*}}\bm{V}^{\star}{}:={\bm{U}}^{\star}{}{\bm{B}^{\star}}$
denote its reduced (rank $r$) SVD, and
$\kappa:={\sigma_{\max}^{\star}}/{\sigma_{\min}^{\star}}$ the condition number
of ${\bm{\Sigma}^{*}}$. We let
${\bm{B}^{\star}}:={\bm{\Sigma}^{*}}\bm{V}^{\star}{}$.

Since no measurement $\bm{y}_{ki}$ is a global function of the entire matrix,
${\bm{X}}^{\star}{}$, we need the following assumption, borrowed from LR
matrix completion literature, to make our problem well-posed (allow for
correct interpolation across columns).

######  Assumption 2.1 (Incoherence of right singular vectors).

Assume that
$\|\bm{b}^{\star}_{k}\|^{2}\leq\mu^{2}r{\sigma_{\max}^{\star}}^{2}/q$ for a
numerical constant $\mu$.

The communication complexity and privacy discussion assumes a vertically
federated setting, i.e., one in which a different subset of $\bm{y}_{k}$s is
measured/sketched at each node.

###  II-B Notation

$\|.\|_{F}$ denotes the Frobenius norm, $\|.\|$ without a subscript denotes
the (induced) $l_{2}$ norm, ⊤ denotes matrix or vector transpose, $\bm{e}_{k}$
is used to denote the $k$-th canonical basis vector ($k$-th column of
$\bm{I}$), and $\bm{M}^{\dagger}:=(\bm{M}^{\top}\bm{M})^{-1}\bm{M}^{\top}$.
For two $n\times r$ matrices ${\bm{U}}_{1},{\bm{U}}_{2}$ that have orthonormal
columns, we use

$\mathrm{SD}_{2}({\bm{U}}_{1},{\bm{U}}_{2}):=\|(\bm{I}-{\bm{U}}_{1}{\bm{U}}_{1}^{\top}){\bm{U}}_{2}\|$

as the Subspace Distance (SD) measure. In our previous work, we used the
Frobenius norm SD,

$\mathrm{SD}_{F}({\bm{U}}_{1},{\bm{U}}_{2}):=\|(\bm{I}-{\bm{U}}_{1}{\bm{U}}_{1}^{\top}){\bm{U}}_{2}\|_{F}.$

Clearly,
$\mathrm{SD}_{F}({\bm{U}}_{1},{\bm{U}}_{2})\leq\sqrt{r}\mathrm{SD}_{2}({\bm{U}}_{1},{\bm{U}}_{2})$.
We reuse the letters $c,C$ to denote different numerical constants in each use
with the convention that $c<1$ and $C\geq 1$. We use $\sum_{k}$ as a shortcut
for the summation over $k=1$ to $q$ and $\sum_{ki}$ for that for the summation
over $i=1$ to $m$ and $k=1$ to $q$.

###  II-C Review of AltGDmin algorithm

AltGDmin, summarized in Algorithm 1, imposes the LR constraint by factorizing
the unknown matrix ${\bm{X}}$ as ${\bm{X}}={\bm{U}}\bm{B}$ with ${\bm{U}}$
being an $n\times r$ matrix and $\bm{B}$ an $r\times q$ matrix. It minimizes
$f({\bm{U}},\bm{B}):=\sum_{k=1}^{q}\|\bm{y}_{k}-{\bm{U}}\bm{b}_{k}\|^{2}$ as
follows:

  1. 1.

Truncated spectral init: Initialize ${\bm{U}}$ (explained below).

  2. 2.

At each iteration, update $\bm{B}$ and ${\bm{U}}$ as follows:

    1. (a)

Min for $\bm{B}$: keeping ${\bm{U}}$ fixed, update $\bm{B}$ by solving
$\min_{\bm{B}}f({\bm{U}},\bm{B})$. Due to the form of the LRCS measurement
model, this minimization decouples across columns, making it a cheap least
squares problem of recovering $q$ different $r$ length vectors. It is solved
as $\bm{b}_{k}=(\bm{A}_{k}{\bm{U}})^{\dagger}\bm{y}_{k}$ for each $k\in[q]$.

    2. (b)

Projected-GD for ${\bm{U}}$: keeping $\bm{B}$ fixed, update ${\bm{U}}$ by a GD
step, followed by orthonormalizing its columns:
${\bm{U}}^{+}=QR({\bm{U}}-\eta\nabla_{{\bm{U}}}f({\bm{U}},\bm{B})))$. Here
$QR(.)$ orthonormalizes the columns of its input.

We initialize ${\bm{U}}$ by computing the top $r$ singular vectors of

${\bm{X}}_{0}:=\sum_{k}\bm{A}_{k}^{\top}\bm{y}_{k,trnc}\bm{e}_{k}^{\top},\
\bm{y}_{k,trnc}:=\mathrm{trunc}(\bm{y}_{k},\alpha)$

Here $\alpha:=\tilde{C}\sum_{k}\|\bm{y}_{k}\|^{2}/mq$ with
$\tilde{C}:=9\kappa^{2}\mu^{2}$. The function trunc truncates (zeroes out) all
entries of $\bm{y}_{k}$ with magnitude greater than $\sqrt{\alpha}$, i.e., for
all $j\in[n]$,
$\mathrm{trunc}(\bm{y},\alpha)_{j}=(\bm{y})_{j}\bm{1}_{|\bm{y}_{j}|\leq\sqrt{\alpha}})$,
with $\bm{1}$ being the indicator function.

Sample-splitting is assumed, i.e., each new update of ${\bm{U}}$ and $\bm{B}$
uses a new independent set of measurements and measurement matrices,
$\bm{y}_{k},\bm{A}_{k}$.

The use of minimization to update $\bm{B}$ at each iteration is what helps
ensure that we can show exponential error decay with a constant step size. At
the same time, due to the decoupling, its time complexity is only as much as
that of computing one gradient w.r.t. ${\bm{U}}$. Both steps need111The LS
step time is $\max(q\cdot mnr,q\cdot mr^{2})=mqnr$ (maximum of the time needed
for computing $\bm{A}_{k}{\bm{U}}$ for all $k$, and that for obtaining
$\bm{b}_{k}$ for all $k$) while the GD step time is $\max(q\cdot
mnr,nr^{2})=mqnr$ (maximum of the time needed for computing the gradient
w.r.t. ${\bm{U}}$, and time for the QR step). time of order $mqnr$. This is
only $r$ times more than “linear time” (time needed to read the algorithm
inputs, here $\bm{y}_{k},\bm{A}_{k}$’s). To our knowledge, $r$-times linear-
time is the best known time complexity for any algorithm for any LR matrix
recovery problem. Moreover, due to the use of the ${\bm{X}}={\bm{U}}\bm{B}$
factorization, AltGDmin is also communication-efficient. Each node needs to
only send $nr$ scalars (gradients w.r.t ${\bm{U}}$) at each iteration.

Algorithm 1 The AltGD-Min algorithm.

1:Input: $\bm{y}_{k},\bm{A}_{k},k\in[q]$

2:Sample-split: Partition the measurements and measurement matrices into
$2T+2$ equal-sized disjoint sets: two sets for initialization and $2T$ sets
for the iterations. Denote these by
$\bm{y}_{k}^{(\tau)},\bm{A}_{k}^{(\tau)},\tau=00,0,1,\dots 2T$.

3:Initialization:

4:Using $\bm{y}_{k}\equiv\bm{y}_{k}^{(00)},\bm{A}_{k}\equiv\bm{A}_{k}^{(00)}$,

5:set
$\alpha\leftarrow\tilde{C}\frac{1}{mq}\sum_{ki}\big{|}\bm{y}_{ki}\big{|}^{2}$,

6:Using $\bm{y}_{k}\equiv\bm{y}_{k}^{(0)},\bm{A}_{k}\equiv\bm{A}_{k}^{(0)}$,

7:set
$\bm{y}_{k,trunc}(\alpha)\leftarrow\bm{y}_{k,trnc}:=\mathrm{trunc}(\bm{y}_{k},\alpha)$,

8:set
$\displaystyle{\bm{X}}_{0}\leftarrow(1/m)\sum_{k\in[q]}\bm{A}_{k}^{\top}\bm{y}_{k,trunc}(\alpha)\bm{e}_{k}^{\top}$

9:set ${\bm{U}}_{0}\leftarrow$ top-$r$-singular-vectors of ${\bm{X}}_{0}$

10:GDmin iterations:

11:for $t=1$ to $T$ do

12: Let ${\bm{U}}\leftarrow{\bm{U}}_{t-1}$.

13: Using $\bm{y}_{k}\equiv\bm{y}_{k}^{(t)},\bm{A}_{k}\equiv\bm{A}_{k}^{(t)}$,

14: set $\bm{b}_{k}\leftarrow(\bm{A}_{k}{\bm{U}})^{\dagger}\bm{y}_{k}$,
$\bm{x}_{k}\leftarrow{\bm{U}}\bm{b}_{k}$ for all $k\in[q]$

15: Using
$\bm{y}_{k}\equiv\bm{y}_{k}^{(T+t)},\bm{A}_{k}\equiv\bm{A}_{k}^{(T+t)}$,
compute

16: set
$\nabla_{\bm{U}}f({\bm{U}},\bm{B})=\sum_{k}\bm{A}_{k}^{\top}(\bm{A}_{k}{\bm{U}}\bm{b}_{k}-\bm{y}_{k})\bm{b}_{k}^{\top}$

17: set
$\displaystyle\hat{\bm{U}}^{+}\leftarrow{\bm{U}}-(\eta/m)\nabla_{\bm{U}}f({\bm{U}},\bm{B}_{t})$.

18: compute
$\hat{\bm{U}}^{+}\overset{\mathrm{QR}}{=}{\bm{U}}^{+}{\bm{R}}^{+}$.

19: Set ${\bm{U}}_{t}\leftarrow{\bm{U}}^{+}$.

20:end for

##  III New Guarantee

Let $m_{0}$ and $m_{1}$ denote the total number of samples per column needed
for initialization and let $m_{1}$ denote this number for each GDmin
iteration. Then, the total sample complexity per column is $m=m_{0}+m_{1}T$.

######  Theorem 3.1.

Assume that Assumption 2.1 holds. Set $\eta=0.4/m{\sigma_{\max}^{\star}}^{2}$
and $T=C\kappa^{2}\log(1/\epsilon)$. If

$mq\geq C\kappa^{6}\mu^{2}(n+q)r(\kappa^{2}r+\log(1/\epsilon))$

and $m\geq C\max(\log n,\log q,r)\log(1/\epsilon)$, then, with probability
(w.p.) at least $1-n^{-10}$,

$\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})\leq\epsilon\text{ and
}\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|\leq\epsilon\|\bm{x}^{\star}_{k}\|\
\text{for all $k\in[q]$}.$

The time complexity is $mqnr\cdot T=C\kappa^{2}mqnr\log(1/\epsilon)$. The
communication complexity is $nr$ per node per iteration.

###### Proof.

We prove the three results needed for proving this in Sections IV-B, IV-D, and
V below. We use these to prove the above result in Sec. VI.∎

###  III-A Discussion

We use $a\gtrsim b$ to mean that $a\geq C_{\kappa,\mu}b$ where
$C_{\kappa,\mu}$ includes terms dependent on $\kappa,\mu$. As done in past
works, our discussion treats $\kappa,\mu$ as numerical constants (that do not
grow with $n,q,r$). Also, whp means w.p. at least $1-n^{-10}$.

Our result from [1] needed

$mq\geq C\kappa^{6}\mu^{2}(n+q)r^{2}\log(1/\epsilon)$

Our new result improves the dependence on $r,\epsilon$ from order
$r^{2}\log(1/\epsilon)$ to order $r\cdot\max(r,\log(1/\epsilon))$. Let
$\mathrm{mx}=\max(r,\log(1/\epsilon))$; then the old one [1] needs $mq\gtrsim
n(\mathrm{mx})^{3}$ while the new one needs $mq\gtrsim n(\mathrm{mx})^{2}$.
This improvement is obtained because our new guarantee for the GD step
(Theorem 4.4) only needs $m_{1}q\gtrsim nr$ at each iteration. On the other
hand, the older result needed $m_{1}q\gtrsim nr^{2}$. Both guarantees need
$m_{0}q\gtrsim nr^{2}$ for initialization, see Theorem 5.7.

We get this improvement because we now use a simpler proof technique that
works for the LRCS problem, but not for its LR phase retrieval (LRPR)
generalization. LRPR involves recovering ${\bm{X}}^{\star}{}$ from
$\bm{z}_{k}:=|\bm{y}_{k}|,k\in[q]$. In [1], we were attempting to solve both
problems. There are two differences in our new proof compared with that of
[1]: (i) we use the 2-norm subspace distance
$\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})$ instead of
$\mathrm{SD}_{F}({\bm{U}},{\bm{U}}^{\star}{})$, and (ii) we do not use the
fundamental theorem of calculus [2, 3] for analyzing the GD step, but instead
use a much simpler direct approach222If we only use (ii) but not (i), we will
still get a simpler proof, but we will not get the sample complexity gain.. In
[1], we used the Frobenius norm SD because it helped obtain the desired
$nr^{3}$ guarantee for LRPR333Our older guarantee for LRPR [1] needed
$mq\gtrsim nr^{2}(r+\log(1/\epsilon))$. If we use the new approach developed
here, it will need $mq\gtrsim nr(r^{3}+\log(1/\epsilon))$.. Also, in
hindsight, the use of the fundamental theorem of calculus was unnecessary. It
has been used in earlier work [3] for analyzing a GD based algorithm for
standard PR and for LR matrix completion and that originally motivated us to
adapt the same approach for LRCS and LRPR.

##  IV New proof: GDmin iterations

###  IV-A Definitions and preliminaries

Let ${\bm{U}}$ be the estimate at the $t$-th iteration. Define

$\displaystyle\bm{g}_{k}$
$\displaystyle:={\bm{U}}^{\top}\bm{x}^{\star}_{k},k\in[q],\text{ and
}\bm{G}:={\bm{U}}^{\top}{\bm{X}}^{\star}{},$ $\displaystyle\bm{P}$
$\displaystyle:=\bm{I}-{\bm{U}}^{\star}{}{\bm{U}}^{\star}{}^{\top},$
$\displaystyle\mathrm{GradU}$
$\displaystyle:=\nabla_{\bm{U}}f({\bm{U}},\bm{B})=\sum_{k}\bm{A}_{k}^{\top}(\bm{A}_{k}{\bm{U}}\bm{b}_{k}-\bm{y}_{k})\bm{b}_{k}^{\top}$
$\displaystyle=\sum_{ki}(\bm{y}_{ki}-\bm{a}_{ki}{}^{\top}{\bm{U}}\bm{b}_{k})\bm{a}_{ki}\bm{b}_{k}{}^{\top}$

For an $n_{1}\times n_{2}$ matrix, ${\bm{{Z}}}$,
$\sigma_{\min}({\bm{{Z}}})=\sigma_{\min}({\bm{{Z}}}^{\top})=\sigma_{\min(n_{1},n_{2})}({\bm{{Z}}})$.
Thus, if $\bm{A}$ is tall, then
$\sigma_{\min}(\bm{A})=\sqrt{\lambda_{\min}(\bm{A}^{\top}\bm{A})}$. Using
this, it follows that, if $\bm{A}=\bm{B}\bm{C}$ and $\bm{A}$ and $\bm{B}$ are
tall (or square), then
$\sigma_{\min}(\bm{A})\geq\sigma_{\min}(\bm{B})\sigma_{\min}(\bm{C})$.

###  IV-B Minimization step

Assume $\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})\leq\delta_{t}$ with
$\delta_{t}<0.02$.

We use the following lemma.

######  Lemma 4.1 ([1]).

Let $\bm{g}_{k}:={\bm{U}}^{\top}\bm{x}^{\star}_{k}.$ Then, w.p. at least
$1-\exp(\log q+r-cm)$,

$\displaystyle\|\bm{g}_{k}-\bm{b}_{k}\|$ $\displaystyle\leq
0.4\|\left(\bm{I}_{n}-{\bm{U}}{\bm{U}}^{\top}\right){\bm{U}}^{\star}{}\bm{b}^{\star}_{k}\|$

By Lemma 4.1, if $m\gtrsim\max(\log q,\log n,r)$, then, whp

$\|\bm{b}_{k}-\bm{g}_{k}\|\leq
0.4\|(\bm{I}-{\bm{U}}{\bm{U}}^{\top}){\bm{U}}^{\star}{}\bm{b}^{\star}_{k}\|$

This directly implies

  1. 1.

$\|\bm{b}_{k}-\bm{g}_{k}\|\leq 0.4\delta_{t}\|\bm{b}^{\star}_{k}\|$

  2. 2.

$\|\bm{b}_{k}\|\leq\|\bm{g}_{k}\|+0.4\cdot 0.02\|\bm{b}^{\star}_{k}\|\leq
1.1\|\bm{b}^{\star}_{k}\|$

  3. 3.

$\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|\leq 1.4\delta_{t}\|\bm{b}^{\star}_{k}\|$

Using above,

$\|\bm{B}-\bm{G}\|_{F}\leq
0.4\delta_{t}\sqrt{\sum_{k}\|\bm{b}^{\star}_{k}\|^{2}}=0.4\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}$

and similarly for $\|{\bm{X}}-{\bm{X}}^{\star}{}\|_{F}$. Thus,

  1. 1.

$\|\bm{B}-\bm{G}\|_{F}\leq 0.4\delta_{t}\|{\bm{B}^{\star}}\|_{F}\leq
0.4\sqrt{r}\delta_{t}{\sigma_{\max}^{\star}}$

  2. 2.

$\|{\bm{X}}-{\bm{X}}^{\star}{}\|_{F}\leq
1.4\sqrt{r}\delta_{t}{\sigma_{\max}^{\star}}$

Furthermore,

$\sigma_{\min}(\bm{B})\geq\sigma_{\min}(\bm{G})-\|\bm{B}-G\|\geq\sigma_{\min}(\bm{G})-\|\bm{B}-G\|_{F}$

We have

$\sigma_{\min}(\bm{G})=\sigma_{\min}(\bm{G}^{\top})\geq{\sigma_{\min}^{\star}}\sigma_{\min}({\bm{U}}^{\star}{}^{\top}{\bm{U}})$

and

$\sigma_{\min}({\bm{U}}^{\star}{}^{\top}{\bm{U}})=\sqrt{1-\|\bm{P}{\bm{U}}\|^{2}}\geq\sqrt{1-\delta_{t}^{2}}$

This follows using
$\sigma_{\min}^{2}({\bm{U}}^{\star}{}^{\top}{\bm{U}})=\lambda_{\min}({\bm{U}}^{\top}{\bm{U}}^{\star}{}{\bm{U}}^{\star}{}^{\top}{\bm{U}})=\lambda_{\min}({\bm{U}}^{\top}(\bm{I}-\bm{P}){\bm{U}})=\lambda_{\min}(\bm{I}-{\bm{U}}^{\top}\bm{P}{\bm{U}})=\lambda_{\min}(\bm{I}-{\bm{U}}^{\top}\bm{P}^{2}{\bm{U}})=1-\lambda_{\max}({\bm{U}}^{\top}\bm{P}^{2}{\bm{U}})=1-\|\bm{P}{\bm{U}}\|^{2}$.

Combining the above three bounds, if $\delta_{t}<0.02/\sqrt{r}\kappa$, then

$\sigma_{\min}(\bm{B})\geq\sqrt{1-\delta_{t}^{2}}{\sigma_{\min}^{\star}}-0.4\sqrt{r}\delta_{t}{\sigma_{\max}^{\star}}\geq
0.9{\sigma_{\min}^{\star}}$

and

$\sigma_{\max}(\bm{B})\leq\|\bm{G}\|+0.4\sqrt{r}\delta_{t}{\sigma_{\max}^{\star}}\leq
1.1{\sigma_{\max}^{\star}}$

since $\|\bm{G}\|\leq\|{\bm{B}^{\star}}\|={\sigma_{\max}^{\star}}$.

Thus, we have proved the following claim:

######  Theorem 4.2.

Assume that $\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})\leq\delta_{t}$. If
$\delta_{t}\leq 0.02/\sqrt{r}\kappa$, and if $m\gtrsim\max(\log q,\log n,r)$,
then whp,

  1. 1.

$\|\bm{b}_{k}-\bm{g}_{k}\|\leq 0.4\delta_{t}\|\bm{b}^{\star}_{k}\|$

  2. 2.

$\|\bm{b}_{k}\|\leq\|\bm{g}_{k}\|+0.4\cdot 0.02\|\bm{b}^{\star}_{k}\|\leq
1.1\|\bm{b}^{\star}_{k}\|$

  3. 3.

$\|\bm{B}-\bm{G}\|_{F}\leq 0.4\delta_{t}\|{\bm{B}^{\star}}\|_{F}\leq
0.4\sqrt{r}\delta_{t}{\sigma_{\max}^{\star}}$

  4. 4.

$\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|\leq 1.4\delta_{t}\|\bm{b}^{\star}_{k}\|$

  5. 5.

$\|{\bm{X}}-{\bm{X}}^{\star}{}\|_{F}\leq
1.4\sqrt{r}\delta_{t}{\sigma_{\max}^{\star}}$

  6. 6.

$\sigma_{\min}(\bm{B})\geq 0.9{\sigma_{\min}^{\star}}$

  7. 7.

$\sigma_{\max}(\bm{B})\leq 1.1{\sigma_{\max}^{\star}}$

(only the last two bounds require the upper bound on $\delta_{t}$).

###  IV-C New bounds on the expected gradient and deviation from it

Using independence of $\bm{A}_{k}$ and $\\{{\bm{U}},\bm{b}_{k}\\}$ (due to
sample splitting),

$\mathbb{E}[\mathrm{GradU}]=\sum_{k}m(\bm{x}_{k}-{\bm{x}^{\star}_{k}})\bm{b}_{k}{}^{\top}$

Using bounds on $\|\bm{B}\|$ and $\|{\bm{X}}^{\star}{}-{\bm{X}}\|_{F}$ from
Theorem 4.2, if $\delta_{t}<\frac{c}{\sqrt{r}\kappa}$,

$\displaystyle\|\mathbb{E}[\mathrm{GradU}]\|$
$\displaystyle=\|\sum_{k}m(\bm{x}_{k}-{\bm{x}^{\star}_{k}})\bm{b}_{k}{}^{\top}\|=m\|({\bm{X}}-{\bm{X}}^{\star}{})\bm{B}^{\top}\|$
$\displaystyle\leq m\|{\bm{X}}-{\bm{X}}^{\star}{}\|\cdot\|\bm{B}\|$
$\displaystyle\leq m\|{\bm{X}}-{\bm{X}}^{\star}{}\|_{F}\cdot\|\bm{B}\|\leq
1.1m\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}^{2}.$

w.p. $1-\exp(\log q+r-cm)$.

Next, we bound
$\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|=\max_{\|\bm{w}\|=1,\|\bm{z}\|=1}\bm{w}^{\top}(\sum_{k}\sum_{i}\bm{a}_{ki}\bm{a}_{ki}^{\top}(\bm{x}_{k}-\bm{x}^{\star}_{k})\bm{b}_{k}^{\top}-\mathbb{E}[\cdot])\bm{z}.$
This also uses independence of $\bm{A}_{k}$ and $\\{{\bm{U}},\bm{b}_{k}\\}$.

We bound the above for fixed unit norm $\bm{w},\bm{z}$ using sub-exponential
Bernstein inequality (Theorem 2.8.1 of [4]). We extend the bound to all unit
norm $\bm{w},\bm{z}$ by using a standard epsilon-net argument. For fixed unit
norm $\bm{w},\bm{z}$, consider

$\sum_{k}\sum_{i}\left((\bm{w}^{\top}\bm{a}_{ki})(\bm{b}_{k}^{\top}\bm{z})\bm{a}_{ki}^{\top}(\bm{x}_{k}-\bm{x}^{\star}_{k})-\mathbb{E}[\cdot]\right)$

Observe that the summands are independent, zero mean, sub-exponential r.v.s
with sub-exponential norm $K_{ki}\leq
C\|\bm{w}\|\cdot|\bm{z}^{\top}\bm{b}_{k}|\cdot\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|=C|\bm{z}^{\top}\bm{b}_{k}|\cdot\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|$.
We apply the sub-exponential Bernstein inequality, Theorem 2.8.1 of [4], with
$t=\epsilon_{1}\delta_{t}m{\sigma_{\min}^{\star}}^{2}$. We have

$\displaystyle\frac{t^{2}}{\sum_{ki}K_{ki}^{2}}$
$\displaystyle\geq\frac{\epsilon_{1}^{2}\delta_{t}^{2}m^{2}{\sigma_{\min}^{\star}}^{4}}{m\sum_{k}\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|^{2}(\bm{z}^{\top}\bm{b}_{k})^{2}}$
$\displaystyle\geq\frac{\epsilon_{1}^{2}\delta_{t}^{2}m^{2}{\sigma_{\min}^{\star}}^{4}}{m\max_{k}\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|^{2}\sum_{k}(\bm{z}^{\top}\bm{b}_{k})^{2}}$
$\displaystyle=\frac{\epsilon_{1}^{2}\delta_{t}^{2}m^{2}{\sigma_{\min}^{\star}}^{4}}{m\max_{k}\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|^{2}\|\bm{z}^{\top}\bm{B}\|^{2}}$
$\displaystyle\geq\frac{\epsilon_{1}^{2}\delta_{t}^{2}m^{2}{\sigma_{\min}^{\star}}^{4}q}{1.4^{2}m\mu^{2}\delta_{t}^{2}r{\sigma_{\max}^{\star}}^{2}\|\bm{B}\|^{2}}$
$\displaystyle\geq\frac{\epsilon_{1}^{2}\delta_{t}^{2}m^{2}{\sigma_{\min}^{\star}}^{4}q}{1.4^{2}m\mu^{2}\delta_{t}^{2}r{\sigma_{\max}^{\star}}^{2}1.1{\sigma_{\max}^{\star}}^{2}}=c\frac{\epsilon_{1}^{2}mq}{\kappa^{4}\mu^{2}r}$
$\displaystyle\frac{t}{\max_{ki}K_{ki}}$
$\displaystyle\geq\frac{\epsilon_{1}\delta_{t}m{\sigma_{\min}^{\star}}^{2}}{\max_{k}\|\bm{b}_{k}\|\max_{k}\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|}\geq
c\frac{\epsilon_{1}mq}{\kappa^{2}\mu^{2}r}$

In the above, we used (i)
$\sum_{k}(\bm{z}^{\top}\bm{b}_{k})^{2}=\|\bm{z}^{\top}\bm{B}\|^{2}\leq\|\bm{B}\|^{2}$
since $\bm{z}$ is unit norm, (ii) Theorem 4.2 to bound $\|\bm{B}\|\leq
1.1{\sigma_{\max}^{\star}}$, and (iii) Theorem 4.2 followed by Assumption 2.1
(right incoherence) to bound
$\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|\leq\delta_{t}\cdot\mu{\sigma_{\max}^{\star}}\sqrt{r/q}$
and $|\bm{z}^{\top}\bm{b}_{k}|\leq\|\bm{b}_{k}\|\leq
1.1\|\bm{b}^{\star}_{k}\|\leq 1.1\mu{\sigma_{\max}^{\star}}\sqrt{r/q}$.

For $\epsilon_{1}<1$, the first term above is smaller (since $1/\kappa^{4}\leq
1/\kappa^{2}$), i.e.,
$\min(\frac{t^{2}}{\sum_{ki}K_{ki}^{2}},\frac{t}{\max_{ki}K_{ki}})=c\frac{\epsilon_{1}^{2}mq}{\kappa^{4}\mu^{2}r}.$
Thus, by sub-exponential Bernstein, w.p. at least
$1-\exp(-c\frac{\epsilon_{1}^{2}mq}{\kappa^{4}\mu^{2}r})-\exp(\log q+r-cm)$,
for a given $\bm{w},\bm{z}$,

$\bm{w}^{\top}(\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}])\bm{z}\leq\epsilon_{1}\delta_{t}m{\sigma_{\min}^{\star}}^{2}$

Using a standard epsilon-net argument to bound the maximum of the above over
all unit norm $\bm{w},\bm{z}$, e.g., using [1, Proposition 4.7], we can
conclude that

$\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|\leq
1.1\epsilon_{1}\delta_{t}m{\sigma_{\min}^{\star}}^{2}$

w.p. at least
$1-\exp(C(n+r)-c\frac{\epsilon_{1}^{2}mq}{\kappa^{4}\mu^{2}r})-\exp(\log
q+r-cm)$. The factor of $\exp(C(n+r))$ is due to the epsilon-net over $\bm{w}$
and that over $\bm{z}$: $\bm{w}$ is an $n$-length unit norm vector while
$\bm{z}$ is an $r$-length unit norm vector. The smallest epsilon net covering
the hyper-sphere of all $\bm{w}$s is of size $(1+2/\epsilon_{net})^{n}=C^{n}$
with $\epsilon_{net}=c$ while that for $\bm{z}$ is of size $C^{r}$. Union
bounding over both thus gives a factor of $C^{n+r}$. By replacing
$\epsilon_{1}$ by $\epsilon_{1}/1.1$, our bound becomes simpler (and
$1/1.1^{2}$ gets incorporated into the factor $c$). We have thus proved the
following.

######  Lemma 4.3.

Assume that $\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})\leq\delta_{t}$. The
following hold:

  1. 1.

$\mathbb{E}[\mathrm{GradU}]=m({\bm{X}}-{\bm{X}}^{\star}{})\bm{B}^{\top}=m({\bm{U}}\bm{B}\bm{B}^{\top}-{\bm{X}}^{\star}{}\bm{B}^{\top})$

  2. 2.

$\|\mathbb{E}[\mathrm{GradU}]\|\leq
1.1m\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}^{2}$

  3. 3.

If $\delta_{t}<\frac{c}{\sqrt{r}\kappa}$, then, w.p. at least
$1-\exp(C(n+r)-c\frac{\epsilon_{1}^{2}mq}{\kappa^{4}\mu^{2}r})-\exp(\log
q+r-cm)$,

$\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|\leq\epsilon_{1}\delta_{t}m{\sigma_{\min}^{\star}}^{2}$

The above lemma is an improvement over the bounds given in [1] because
$\delta_{t}$ is now the bound on the 2-norm SD, and still it only needs
$mq\gtrsim nr/\epsilon_{1}^{2}$.

###  IV-D GD step

Assume that $\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})\leq\delta_{t}$ with
$\delta_{t}<0.02$.

Recall the Projected GD step for ${\bm{U}}$:

$\displaystyle\widetilde{\bm{U}}^{+}$
$\displaystyle={\bm{U}}-\eta\mathrm{GradU}\text{ and
}\widetilde{\bm{U}}^{+}\overset{\mathrm{QR}}{=}{\bm{U}}^{+}{\bm{R}}^{+}$

Since ${\bm{U}}^{+}=\widetilde{\bm{U}}^{+}({\bm{R}}^{+})^{-1}$ and since
$\|({\bm{R}}^{+})^{-1}\|=1/\sigma_{\min}({\bm{R}}^{+})=1/\sigma_{\min}(\widetilde{\bm{U}}^{+})$,
thus,
$\mathrm{SD}_{2}({\bm{U}}^{+},{\bm{U}}^{\star}{})=\|\bm{P}{\bm{U}}^{+}\|$ can
be bounded as

$\displaystyle\mathrm{SD}_{2}({\bm{U}}^{+},{\bm{U}}^{\star}{})$
$\displaystyle\leq\dfrac{\|\bm{P}\widetilde{\bm{U}}^{+}\|}{\sigma_{\min}(\widetilde{\bm{U}}^{+})}\leq\dfrac{\|\bm{P}\widetilde{\bm{U}}^{+}\|}{\sigma_{\min}({\bm{U}})-\eta\|\mathrm{GradU}\|}$
(2)

Consider the numerator. Adding/subtracting $\mathbb{E}[\mathrm{GradU}]$, left
multiplying both sides by $\bm{P}$, and using Lemma 4.3 (first part),

$\displaystyle\tilde{\bm{U}}^{+}$
$\displaystyle={\bm{U}}-\eta\mathbb{E}[\mathrm{GradU}]+\eta(\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU}),\text{
thus,}$ $\displaystyle\bm{P}\tilde{\bm{U}}^{+}$
$\displaystyle=\bm{P}{\bm{U}}-\eta
m\bm{P}{\bm{U}}\bm{B}\bm{B}^{\top}+\eta\bm{P}(\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU})$

The last row used $\bm{P}{\bm{X}}^{\star}{}=0$. Thus,

$\displaystyle\|\bm{P}\tilde{\bm{U}}^{+}\|\leq\|\bm{P}{\bm{U}}\|\|\bm{I}-\eta
m\bm{B}\bm{B}^{\top}\|+\eta\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU}\|$ (3)

Using Theorem 4.2, we get

$\lambda_{\min}(\bm{I}-\eta m\bm{B}\bm{B}^{\top})=1-\eta m\|\bm{B}\|^{2}\geq
1-1.2\eta m{\sigma_{\max}^{\star}}^{2}$

Thus, if $\eta<0.5/m{\sigma_{\max}^{\star}}^{2}$, then the above matrix is
p.s.d. This along with Theorem 4.2 then implies that

$\|\bm{I}-\eta m\bm{B}\bm{B}^{\top}\|=\lambda_{\max}(\bm{I}-\eta
m\bm{B}\bm{B}^{\top})\leq 1-0.9\eta m{\sigma_{\min}^{\star}}^{2}$

Using the above, (3), and the bound on
$\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU}\|$ from Lemma 4.3, we conclude
the following: If $\eta\leq 0.5/m{\sigma_{\max}^{\star}}^{2}$, and
$\delta_{t}\leq c/\sqrt{r}\kappa$, then

$\displaystyle\|\bm{P}\tilde{\bm{U}}^{+}\|$
$\displaystyle\leq\|\bm{P}{\bm{U}}\|\|\bm{I}-\eta
m\bm{B}\bm{B}^{\top}\|+\eta\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU}\|$
$\displaystyle\leq\delta_{t}(1-0.9~{}\eta m{\sigma_{\min}^{\star}}^{2})+\eta
m\epsilon_{1}\delta_{t}{\sigma_{\min}^{\star}}^{2}$ (4)

w.p. at least
$1-\exp(C(n+r)-c\frac{\epsilon_{1}^{2}mq}{\kappa^{4}\mu^{2}r})-\exp(\log
q+r-cm)$. This probability is at least $1-n^{-10}$ if
$mq\gtrsim\kappa^{4}\mu^{2}nr/\epsilon_{1}^{2}$ and $m\gtrsim\max(\log n,\log
q,r)$.

Next we use (4) with $\epsilon_{1}=0.1$ and Lemma 4.3 in (2). Set
$\eta=c_{\eta}/m{\sigma_{\max}^{\star}}^{2}$. If $c_{\eta}\leq 0.5$, if
$\delta_{t}\leq c/\sqrt{r}\kappa^{2}$, and lower bounds on $m$ from above
hold, (2) implies that, whp,

$\displaystyle\mathrm{SD}_{2}({\bm{U}}^{+},{\bm{U}}^{\star}{})$
$\displaystyle\leq\dfrac{\|\bm{P}\widetilde{\bm{U}}^{+}\|}{\sigma_{\min}({\bm{U}})-\eta\|\mathrm{GradU}\|}$
$\displaystyle\leq\frac{\delta_{t}(1-\eta
m{\sigma_{\min}^{\star}}^{2}(0.9-0.1))}{\sigma_{\min}({\bm{U}})-\eta\|\mathbb{E}[\mathrm{GradU}]\|-\eta\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|}$
$\displaystyle\leq\frac{\delta_{t}(1-0.8\eta
m{\sigma_{\min}^{\star}}^{2})}{1-\eta
m\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}^{2}(1.4+\frac{0.1}{\kappa^{2}\sqrt{r}})}$
$\displaystyle\leq\frac{\delta_{t}(1-0.8\eta
m{\sigma_{\min}^{\star}}^{2})}{1-1.5\eta
m\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}^{2}}$
$\displaystyle\leq\delta_{t}(1-0.8\eta m{\sigma_{\min}^{\star}}^{2})(1+1.5\eta
m\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}^{2})$
$\displaystyle\leq\delta_{t}(1-0.8\eta m{\sigma_{\min}^{\star}}^{2}+1.5\eta
m\delta_{t}\sqrt{r}{\sigma_{\max}^{\star}}^{2})$
$\displaystyle=\delta_{t}(1-\eta
m{\sigma_{\min}^{\star}}^{2}(0.8-1.5\delta_{t}\sqrt{r}\kappa^{2}))$
$\displaystyle\leq\delta_{t}(1-\eta m{\sigma_{\min}^{\star}}^{2}(0.8-0.15))$
$\displaystyle\leq\delta_{t}(1-0.6\eta
m{\sigma_{\max}^{\star}}^{2}/\kappa^{2})=\delta_{t}(1-0.6c_{\eta}/\kappa^{2})$

In the above we used $\kappa^{2}\sqrt{r}>1$, $(1-x)^{-1}<(1+x)$ if $|x|<1$,
and $\delta_{t}<0.1/\sqrt{r}\kappa^{2}$ (used in second-last inequality).

Thus, we have proved the following result.

######  Theorem 4.4.

Assume that Assumption 2.1 holds and
$\mathrm{SD}_{2}({\bm{U}},{\bm{U}}^{\star}{})\leq\delta_{t}$. If
$\delta_{t}\leq 0.02/\sqrt{r}\kappa^{2}$, if
$\eta=c_{\eta}/m{\sigma_{\max}^{\star}}^{2}$ with $c_{\eta}\leq 0.5$, and if
$mq\gtrsim\kappa^{4}\mu^{2}nr$ and $m\gtrsim\max(\log n,\log q,r)$, then, whp

$\mathrm{SD}_{2}({\bm{U}}^{+},{\bm{U}}^{\star}{})\leq\delta_{t+1}:=\delta_{t}(1-0.6c_{\eta}/\kappa^{2})$

##  V New proof: Initialization

We need a new result for the initialization step because we need a tight bound
on $\mathrm{SD}_{2}({\bm{U}}_{0},{\bm{U}}^{\star}{})$.

###  V-A Results taken from [1]

Recall from Algorithm 1 that $\alpha$ uses a different set of measurements
that is independent of those used for ${\bm{X}}_{0}$. We use the following
four results from [1].

######  Lemma 5.1 ([1]).

Conditioned on $\alpha$, we have the following conclusions. Let $\zeta$ be a
scalar standard Gaussian r.v.. Define

$\beta_{k}(\alpha):=\mathbb{E}[\zeta^{2}\mathbbm{1}_{\\{\|\bm{x}^{\star}_{k}\|^{2}\zeta^{2}\leq\alpha\\}}].$

Then,

$\displaystyle\mathbb{E}[{\bm{X}}_{0}|\alpha]={\bm{X}}^{\star}{}{\bm{D}}(\alpha),$
$\displaystyle\text{ where
}{\bm{D}}(\alpha):=diagonal(\beta_{k}(\alpha),k\in[q])$

i.e. ${\bm{D}}(\alpha)$ is a diagonal matrix of size $q\times q$ with diagonal
entries $\beta_{k}$ defined above.

######  Fact 5.2 ([1]).

Let

$\mathcal{E}:=\left\\{\tilde{C}(1-\epsilon_{1})\frac{\|{\bm{X}}^{\star}{}\|_{F}^{2}}{q}\leq\alpha\leq\tilde{C}(1+\epsilon_{1})\frac{\|{\bm{X}}^{\star}{}\|_{F}^{2}}{q}\right\\}.$

$\Pr(\alpha\in\mathcal{E})\geq 1-\exp(-\tilde{c}mq\epsilon_{1}^{2})$. Here
$\tilde{c}=c/\tilde{C}=c/\kappa^{2}\mu^{2}.$

######  Fact 5.3 ([1]).

For any $\epsilon_{1}\leq 0.1$,
$\min_{k}\mathbb{E}\left[\zeta^{2}\mathbbm{1}_{\left\\{|\zeta|\leq\tilde{C}\frac{\sqrt{1-\epsilon_{1}}\|{\bm{X}}^{\star}{}\|_{F}}{\sqrt{q}\|\bm{x}^{\star}_{k}\|}\right\\}}\right]\geq
0.92.$

######  Lemma 5.4 ([1]).

Fix $0<\epsilon_{1}<1$. Then, w.p. at least
$1-\exp\left[(n+q)-c\epsilon_{1}^{2}mq/\mu^{2}\kappa^{2}\right]$, conditioned
on $\alpha$, for an $\alpha\in\mathcal{E}$,

$\|{\bm{X}}_{0}-\mathbb{E}[{\bm{X}}_{0}|\alpha]\|\leq
1.1\epsilon_{1}\|{\bm{X}}^{\star}{}\|_{F}$

Facts 5.2 and 5.3 together imply that, w.p. at least
$1-\exp(-\tilde{c}mq\epsilon_{1}^{2})$,

$\displaystyle\min_{k}\beta_{k}(\alpha)\geq\min_{k}\mathbb{E}\left[\zeta^{2}\mathbbm{1}_{\\{|\zeta|\leq\tilde{C}\frac{\sqrt{1-\epsilon_{1}}\|{\bm{X}}^{\star}{}\|_{F}}{\sqrt{q}\|\bm{x}^{\star}_{k}\|}\\}}\right]\geq
0.92.$ (5)

The first inequality is an immediate consequence of Fact 5.2
($\alpha\in\mathcal{E}$) and the second follows by Fact 5.3.

By setting $\epsilon_{1}=\epsilon_{0}/1.1\sqrt{r}\kappa$ in Lemma 5.4, and
using Fact 5.2, we get the following corollary.

######  Corollary 5.5.

Fix $0<\epsilon_{1}<1$. Then, w.p. at least
$1-\exp\left[(n+q)-c\frac{\epsilon_{0}^{2}mq}{\mu^{2}\kappa^{4}r}\right]-\exp(-cmq\epsilon_{1}^{2}/\kappa^{2}\mu^{2})$,

$\|{\bm{X}}_{0}-\mathbb{E}[{\bm{X}}_{0}|\alpha]\|\leq\epsilon_{0}{\sigma_{\min}^{\star}}$

with $\mathbb{E}[{\bm{X}}_{0}|\alpha]$ being as given on Lemma 5.1.

###  V-B Obtaining the SD error bound for initialization

By Lemma 5.1,
$\mathbb{E}[{\bm{X}}_{0}|\alpha]={\bm{X}}^{\star}{}{\bm{D}}(\alpha)$ with
${\bm{D}}(\alpha)$ as defined there. Clearly, its rank is $r$ or less. To
obtain the bound, we apply Wedin’s $\sin\theta$ theorem [5] for
$\mathrm{SD}_{2}$ with $\bm{M}={\bm{X}}_{0}$,
$\bm{M}^{*}=\mathbb{E}[{\bm{X}}_{0}|\alpha]={\bm{X}}^{\star}{}{\bm{D}}$.
Recall that ${\bm{U}}_{0}$ is the matrix of top $r$ singular vectors of
${\bm{X}}_{0}$. Also, the span of top $r$ singular vectors of
$\mathbb{E}[{\bm{X}}_{0}|\alpha]={\bm{X}}^{\star}{}{\bm{D}}$ equals the column
span of ${\bm{U}}^{\star}{}$. Thus applying Wedin will help us bound
$\mathrm{SD}_{2}({\bm{U}}_{0},{\bm{U}}^{\star}{})$. To do this, we need to
define the SVD of $\mathbb{E}[{\bm{X}}_{0}|\alpha]$. Let

$\mathbb{E}[{\bm{X}}_{0}|\alpha]={\bm{X}}^{\star}{}{\bm{D}}(\alpha)\overset{\mathrm{SVD}}{=}({\bm{U}}^{\star}{}{\bm{Q}})\check{\bm{\Sigma}^{*}}\check{\bm{V}}$

where ${\bm{Q}}$ is a $r\times r$ unitary matrix, $\check{\bm{\Sigma}^{*}}$ is
an $r\times r$ diagonal matrix with non-negative entries (singular values) and
$\check{\bm{V}}$ is an $r\times q$ matrix with orthonormal rows, i.e.
$\check{\bm{V}}\check{\bm{V}}^{\top}=\bm{I}$. Observe also that
$\sigma_{r+1}(\mathbb{E}[{\bm{X}}_{0}|\alpha])=0$ since it is a rank $r$
matrix. Also, from above,

$\sigma_{r}(\mathbb{E}[{\bm{X}}_{0}|\alpha])=\sigma_{\min}(\check{\bm{\Sigma}^{*}})\geq{\sigma_{\min}^{\star}}\sigma_{\min}({\bm{D}})={\sigma_{\min}^{\star}}\min_{k}\beta_{k}(\alpha)$

This follows since
$\check{\bm{\Sigma}^{*}}={\bm{Q}}^{\top}{\bm{B}^{\star}}{\bm{D}}\check{\bm{V}}^{\top}$
and so
$\sigma_{\min}(\check{\bm{\Sigma}^{*}})\geq\sigma_{\min}({\bm{B}^{\star}}{\bm{D}}\check{\bm{V}}^{\top})\geq\sigma_{\min}({\bm{B}^{\star}}{\bm{D}})\cdot
1\geq\sigma_{\min}({\bm{D}}{\bm{B}^{\star}}^{\top})\geq\sigma_{\min}({\bm{D}})\cdot{\sigma_{\min}^{\star}}$
and $\sigma_{\min}({\bm{D}})=\min_{k}\beta_{k}$. The last equality follows
since ${\bm{D}}$ is diagonal with entries $\beta_{k}$. Thus,

######  Fact 5.6.

$\sigma_{r}(\mathbb{E}[{\bm{X}}_{0}|\alpha])\geq{\sigma_{\min}^{\star}}\min_{k}\beta_{k}(\alpha)$,
$\sigma_{r+1}(\mathbb{E}[{\bm{X}}_{0}|\alpha])=0$.

Applying Wedin’s $\sin\theta$ theorem, and then using Corollary 5.5, Fact 5.6
and (5), we get

$\displaystyle\mathrm{SD}_{2}({\bm{U}}_{0},{\bm{U}}^{\star}{})$
$\displaystyle\leq\sqrt{2}\frac{\max(\|({\bm{X}}_{0}-\mathbb{E}[{\bm{X}}_{0}|\alpha])^{\top}{\bm{U}}^{\star}{}\|,\|({\bm{X}}_{0}-\mathbb{E}[X_{0}|\alpha])\check{\bm{V}}\|)}{{\sigma_{\min}^{\star}}\min_{k}\beta_{k}(\alpha)-0-\|{\bm{X}}_{0}-\mathbb{E}[X_{0}|\alpha]\|}$
$\displaystyle\lesssim\sqrt{2}\frac{\epsilon_{0}{\sigma_{\min}^{\star}}}{0.92{\sigma_{\min}^{\star}}-\epsilon_{0}{\sigma_{\min}^{\star}}}\lesssim\sqrt{2}\frac{\epsilon_{0}}{0.9}<1.6\epsilon_{0}$

if $\epsilon_{0}<0.02$ and $mq\gtrsim(n+q)r/\epsilon_{0}^{2}$. In the above we
used
$\|({\bm{X}}_{0}-\mathbb{E}[{\bm{X}}_{0}|\alpha])^{\top}{\bm{U}}^{\star}{}\|\leq\|{\bm{X}}_{0}-\mathbb{E}[X_{0}|\alpha]\|\cdot
1$ and
$\|({\bm{X}}_{0}-\mathbb{E}[{\bm{X}}_{0}|\alpha])\check{\bm{V}}\|\leq\|{\bm{X}}_{0}-\mathbb{E}[X_{0}|\alpha]\|\cdot
1$. Setting $\epsilon_{0}=0.5\delta_{0}$ with $\delta_{0}<0.02$, we obtain our
desired result.

######  Theorem 5.7.

Assume that Assumption 2.1 holds. Pick a $\delta_{0}\leq 0.02$. If
$mq\gtrsim\kappa^{4}\mu^{2}(n+q)r/\delta_{0}^{2}$ then whp

$\mathrm{SD}_{2}({\bm{U}}_{0},{\bm{U}}^{\star}{})\leq\delta_{0}$

##  VI Proof of Theorem 3.1

Theorem 5.7 tells us that
$\mathrm{SD}_{2}({\bm{U}}_{0},{\bm{U}}^{\star}{})\leq\delta_{0}$ whp if
$m_{0}q\gtrsim(n+q)r/\delta_{0}^{2}$. Theorem 4.4 tells us that if
$\delta_{t}\leq 0.02/\sqrt{r}\kappa^{2}$, and if $m_{1}q\gtrsim nr$, then,
whp, $\delta_{t}$ reduces by a factor of $(1-0.6c_{\eta}/\kappa^{2})$ at each
iteration. In particular, this implies that $\delta_{t}\leq\delta_{0}$. Thus,
in order to apply Theorem 4.4, it suffices to require
$\delta_{0}=0.02/\sqrt{r}\kappa^{2}$.

Combining both results, we have shown that if $m_{0}q\geq
C\kappa^{8}\mu^{2}(n+q)r^{2}$ and if $m_{1}q\geq C\kappa^{4}mu^{2}nr$ and
$m_{1}\geq C\max(r,\log n,\log r)$, and if
$\eta=c_{\eta}/(m{\sigma_{\max}^{\star}}^{2})$ with $c_{\eta}<0.5$, then, whp,
at each $t\geq 0$,

$\mathrm{SD}_{2}({\bm{U}}_{t},{\bm{U}}^{\star}{})\leq\delta_{t}:=(1-0.6\frac{c_{\eta}}{\kappa^{2}})^{t}\delta_{0}=(1-0.6\frac{c_{\eta}}{\kappa^{2}})^{t}\frac{0.02}{\sqrt{r}\kappa^{2}}$

and all bounds of Theorem 4.2 hold with $\delta_{t}$ as above.

Thus, to guarantee
$\mathrm{SD}_{2}({\bm{U}}_{T},{\bm{U}}^{\star}{})\leq\epsilon$, we need

$T\geq C\frac{\kappa^{2}}{c_{\eta}}\log(1/\epsilon)$

This follows by using $\log(1-x)<-x$ for $|x|<1$ and using
$\kappa^{2}\sqrt{r}\geq 1$. Thus, setting $c_{\eta}=0.4$, our sample
complexity $m=m_{0}+m_{1}T$ becomes $mq\geq
C\kappa^{8}\mu^{2}(n+q)r(1+\log(1/\epsilon)),$ and $m\geq C\max(r,\log q,\log
n)\log(1/\epsilon)$.

## References

  * [1] S. Nayer and N. Vaswani, “Fast and sample-efficient federated low rank matrix recovery from column-wise linear and quadratic projections,” _IEEE Trans. Info. Th._ , Feb. 2023.
  * [2] S. Lang, _Real and Functional Analysis_. Springer-Verlag, New York 10:11–13, 1993.
  * [3] C. Ma, K. Wang, Y. Chi, and Y. Chen, “Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution,” in _Intl. Conf. Machine Learning (ICML)_ , 2018.
  * [4] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge University Press, 2018, vol. 47.
  * [5] P.-Å. Wedin, “Perturbation bounds in connection with singular value decomposition,” _BIT Numerical Mathematics_ , vol. 12, no. 1, pp. 99–111, 1972.


# A Zynq-–based flexible ADC architecture combining real-time data streaming
and transient recording

A. Rigoni, G. Manduchi, M. Gottado, R. Cavazzana, M. Recchia, C. Taliercio, A.
Luchetta  Consorzio RFX, Corso Stati Uniti 4, Padova 35127, Italy

###### Abstract

The RFX-mod2 Nuclear Fusion experiment is an upgrade of RFX-mod, shutdown in
2016. Among the other improvements in the machine structure and diagnostics, a
larger number of electromagnetic probes (EMs) is foreseen to provide more
information about plasma instabilities and to allow an improved real-time
plasma control. An Analog to Digital Converter (ADC) architecture able to
provide at the same time both transient recording and real-time streaming, as
well as FPGA-based time integration of the inputs is foreseen in RFX-mod2.
Transient recording provides full speed data acquisition (up to 1 MSample/s)
by recording data in local memory and reading memory content after the plasma
discharge. Real-time streaming of sub-sampled data is required for active
control. The chosen technology is based on the XILINX Zynq architecture that
provides in the same chip a multi-core ARM processor tightly coupled to a
FPGA. Time critical functions are carried out by the FPGA, such as the
management of the circular data buffer, low pass filtering for subsampling of
the samples to be streamed and digital integration. Other functions are
carried out by the processor, such as the management of the configuration
setting, received via TCP/IP or HTTP, the data readout of acquired samples in
transient recording buffers and network data streaming of data collected for
active real-time plasma control.

##  I Introduction

RFX-mod [1] is a medium size toroidal plasma multi-configuration machine
(major radius $R=2.0m$, minor radius $a=0.46m$, operated up to 2 MA current
reversed field pinch (RFP) configuration or 0.5 T tokamak). The experiment was
shut down in 2016 and is now being upgraded as RFX-mod2 [2]. A major foreseen
development is a substantial improvement of the magnetic measurement system.
In the new experiment configuration many of the EM sensors will be moved
inside the vacuum vessel widening their usable signal bandwidth up to 200 kHz
in order to providing better plasma control. Moreover, the total number of the
new magnetic pick-up coil sensors will be increased with the aim of improved
spatial resolution [3].

In order to collect magnetic field measurements from EM probes, analog
integration system [4] was implemented in RFX-mod, followed by two separate
sets of ADC channels, one for precision off-line transient data and the other
for real-time control. Re-implementing the same front-end for an increased
number of channels is costly, requiring enhanced analog integration and
duplication in ADC channels. A more compact and cost effective solution is
being investigated [5], using a configurable FPGA to handle ADC conversion and
providing a set of on-line functions directly performed at the FPGA logic
level, including the numeric integration in real-time, recording at the same
time the dB/dt signals deriving directly from EM coils needed to study the
Magneto Hydro Dynamic (MHD) processes taking place into the plasma [6] [7].
The possibility of directly acquiring the time derivative of the
electromagnetic fields, i.e. the direct signals from EM probes, was not
present in the previous system, acquiring integrated signals in order to
reduce the number of required ADC channels. This fact introduced a severe
limitation in the derivative control required for MHD stabilization because of
the bad quality of the computed time derivative.

The proposed approach will further reduce the number of ADC channels by
merging high frequency transient recording in local memory (up to 1 MHz) and
lower frequency streaming (up to 10 kHz) required for real-time plasma control
and having a single ADC channel performing both. In RFX-mod a fixed subset of
signals from EM probes was used for the active plasma control, requiring a new
set of ADC converters in respect to the transient recorders used for data
acquisition. In RFX-mod2 it will be possible to re-use any ADC channel from EM
probes for real-time plasma control, being the actual number possibly limited
by other factors not related to the ADC devices, such as network bandwidth or
control computation load.

The flexibility provided by a configurable on board FPGA allows also the
inclusion of more sophisticated triggering mechanisms and a deeper integration
with the timing systems. Examples of triggering mechanism are given by the
acquisition of fast transients requiring high speed sampling only in a given,
dynamic Region of Interest (ROI). This feature has been implemented in the
first proof-of-concept device described in a later section. Deeper integration
with the timing systems imply the ability of getting the clock and the trigger
signals not only from digital inputs, but also from the specifically coded
signal carrying both clock and trigger information (timing highway)[8]. Such
signals were used in the RFX-mod timing systems to distribute a synchronous
clock and asynchronous triggers and a timing device was required for every ADC
rack to extract the clock and the trigger signals. The timing device is no
more required for a rack hosting the new ADC devices because the ADC devices
can directly extract timing information from the timing highway.

The adoption of a System on Chip (SoC) based technology exploiting both an ARM
based processing unit and a FPGA logic provides the flexibility of a
configurable device for real-time operations and as well as the possibility of
deploying software components directly on-board. The Red Pitaya board [9] is
currently used for the development of the architecture. A different solution
is however foreseen for the production system integrating an external ADC
section with the Zynq-based SoC board. An ADC front end, already used in other
applications of real-time plasma control [10] was initially considered, but
its noise characteristics, and in particular the noise dependency on
frequency, proved to limit the quality of digital integration. For this
reason, a different solution for the ADC stage is being considered.

The paper is organized as follows: section 2 introduces the reasons for the
choice of the Zynq SoC and summarizes the development process. The complete
development is orchestrated by the ANACLETO [11] framework providing a
seamless integration of the different components (VIVADO XILINX tool,
compilers, makefiles, …) required for both FPGA HDL programming and GNU Linux
driver development.
Section 3 presents the implementation of the ADC flexible architecture
providing support for signal integration, subsampling for real-time streaming,
ROI detection and timing extraction. Section 4 presents the required ADC noise
characteristics and discusses the limitations found in existing
implementation, along with possible solutions. Section 5 presents a proof-of-
concept system developed under ANACLETO on the Red Pitaya board and providing
streamed event-driven high speed data acquisition. Even if not covering all
the presented features, this system has been successfully adopted in the NIO
negative ion beam experiment [12], a satellite experiment of RFX for the study
of additional heating in fusion devices.

##  II The ANACLETO framework for SoC development

As stated before, the RFX-mod2 improved controllability will require the
design of a new ADC architecture able to provide both transient recording and
real-time streaming. The transient recorder functionality will provide full
speed data acquisition (up to $1\approx 2$ MSample/s) by recording data in
local memory and reading back the memory content after the plasma discharge.
At the same time the Real-time streaming is required when the target signal is
used in active control because such data must be promptly available in the
closed loop feedback. In this case a 10 kHz sub-sampled version is streamed
out toward the control units. The solution proposed comes form the adoption of
the technology based on the XILINX Zynq architecture that provides in the same
chip a multi-core ARM processor tightly coupled to an FPGA. The combined usage
of FPGA and a processing unit (running GNU Linux) allows partitioning of the
system functionalities into time-critical components mapped onto the FPGA,
letting the processor address less critical and possibly more complex
functions. Developing critical and non critical functions requires HDL
development for the first ones, and C or C++ code development for the others.
In addition, a GNU Linux driver must be written, acting as a bridge between
the FPGA functions and the outside world. Several tools are available from
XILINX, including the VIVADO framework for the development and integration of
the HDL code into the Zynq architecture, the toolchain required to compile the
driver and the support code in the Zynq processor (dual core ARM) and the
linux code for that processor. Even if the various components are available,
getting them from the proper sources over the network, installing the tools
and building the toolchain is a complicated and error-prone process. The
ANACLETO framework provides an effective solution by transparently
orchestrating the download and the installation of the required components and
toolchain, letting the developer concentrate on the specific aspects of
his/her project. The project specific tasks, i.e. the development of the HDL
code for the FPGA components and their assembly into the firmware project
cannot of course be carried out by the ANACLETO, but the framework provides
useful hints for the development of the linux driver. This is achieved by
ANACLETO by recognizing in the FPGA project what are the components used for
the communication with the processor, and producing generic driver templates
implementing the communication with the I/O components defined in the FPGA
project. Any combination of the following is supported by ANACLETO:

  * •

I/O registers

  * •

Input and/or output FIFOs

  * •

Input and/or output DMA

ANACLETO recognizes the I/O registers, FIFOs and DMA controllers defined in
the FPGA project (available as IPs in the XILINX toolbox), modifies the device
tree produced by VIVADO and produces the corresponding source code driver
template. Of course, no specific functionality can be provided in the driver
templates, except for Input and Output data flow management. Starting from the
template, the developer will implement the specific functions, but he can
ignore to a large extent the intricacies required for the I/O data transfer
such as Interrupt handler programming and DMA engine configuration.

##  III Flexible ADC SoC implementation

The first implementation of the flexible ADC architecture has been carried out
on a Red Pitaya board, using the in-board ADC channels. Even if not intended
to represent the final application, development of FPGA logic on Red Pitaya
offers the advantage of a ready-to-use ADC channel for development and first
tests. Most of the firmware will be retained in the final implementation,
using a different ADC front end.

The time critical functions carried out by the FPGA in this context are:

  * •

The management of a circular data buffer and the DMA transfer in RAM of pre
and post trigger samples after the trigger has been received;

  * •

anti-aliasing filtering and subsequent sub-sampling of the samples to be
streamed. The resulting samples are enqueued in a FIFO accessed by the
processor;

  * •

digital integration for deriving magnetic field measurements from EM probe
signals. Observe that in this case a single ADC stage will generate two ADC
channels;

  * •

ROI detection in case ADC triggers are derived from the signal itself (e.g.
over a given signal level threshold);

  * •

Clock and trigger extraction in case a highway signal is provided by the
timing system, encoding both clock an triggers.

The less critical functions that will be carried out by the processor unit
are:

  * •

The management of the configuration setting, received via TCP/IP or HTTP. The
processor validates the configuration and write the appreciate registers in
the FPGA;

  * •

off-line data readout of acquired samples in transient recording and
communication via TCP/IP with the central data acquisition system;

  * •

network data streaming of sub-sampled data read from the FIFO and sent in UDP
packets to the active plasma control system.

In addition to pre-configured blocks from the XILINX toolbox for data
buffering, DMA engine, I/O FIFO and registers, three blocks implemented in
VHDL carry out the underlying logic. The first block provides the management
of clock and triggers that may be either directly derived from digital inputs
or rebuild by properly decoding the timing highway input signal. The second
block provides programmable input signal elaboration such as low pass
filtering for subsampling and integration. The third block will handle the
triggering logic and the circular buffer holding pre and post trigger samples.
In particular, the trigger may be derived from external signals (via the first
block) or derived from the input signal (e.g. when the input level is greater
than a given threshold).

Communication of subsamples streamed data for real-time plasma control is
achieved using the XILINX AXI Stream FIFO. The Xilinx AXI Stream FIFO is a
Xilinx free software IP that implement a read/write FIFO queue with a well
defined communication protocol. A proper connected IRQ line is used to trigger
events to the processing unit together with the related set of status and
enable registers. In this way data samples are readily available to the linux
processor and will be sent using low latency UDP communication to computing
nodes carrying out distributer for real-time plasma control. Communication of
the data acquired at high speed in the ROI is carried out by a DMA engine,
using circular DMA buffers in order to minimize the number of data copies. In
this case data will be sent to the central Data Acquisition system via TCP/IP
as soon as a ROI has been acquired. Fig. 1 shows the main blocks of the ADC
device: the external ADC circuitry, communicating with the FPGA via a serial
LVDS link; the FPGA logic, communicating with the processor via registers,
FIFO and DMA; the processor components, in kernel and user space.

Figure 1: Logic design of the flexible ADC structure.

##  IV Noise requirements in ADC stage for digital integration

The Red-Pitaya board, hosting two fast ADC inputs, is currently used for the
development of the HDL code and the GNU Linux drivers. Even if it represents a
flexible and cheap solution for development, Red-Pitaya is not foreseen in the
final production stage. In particular, the strict requests in terms of
electrical insulation and noise shape, in order to carry out digital
integration, are not met by the converters mounted in this device. A first
prototype has been implemented using a compact and cost effective front end
and ADC conversion solution based on the ATCA-MIMO-ISOL [13] architecture that
was used for the plasma column vertical stabilization at JET tokamak
experiment. The ADC stage is composed by a plug-in component mounting a 18-bit
SAR converter from Analog Devices (AD7641) that acquires signals from a fully
differential input in the range 2.048 V at a maximum rate of 2 Msps. The
analog input is initially filtered by a 1 pole, 100 kHz passive component
connected to an input range adapter (THS4520), then the ADC converter (AD7641)
is configured to operate using a 4-wires communication protocol and the
electrical insulation is applied to the digital serial data output. The module
is completely insulated from the FPGA and the power is supplied through a
DC/DC converter. A custom logic has been developed in FPGA to implement the
used LVDS serial communication protocol.

The noise introduced by the ADC front end proved not acceptable for performing
numerical integration over a period of some ($<$10) seconds, that is the
expected requested integration period in RFX-mod2. The reason is due to the
introduced 1/f shaped noise, as shown in Fig. 2. We measured also the noise
after bypassing the low pass filter and the impedance adapter, also shown in
Fig.2, that turned out to be one order of magnitude less. In a test performed
under this condition, the quality of reconstruction of an applied magnetic
field collected by a EM probe and integrated in FPGA turned out to be
acceptable (Fig. 3). A set of candidate components, whose noise
characteristics are compatible with the latter noise level, has been
considered for the anti-aliasing filter, the impedance adapter and the ADC
converter and the selected components will be used for the development of of a
new ADC front end component.

Figure 2: Noise spectra. Figure 3: test of numerical integrated signal from
actual probe with real field applied.

##  V A proof-of-concept implementation: fast streamed event driven data
acquisition for the NIO negative ion beam

Another desired topics for a DAQ device is the possibility to increase the
level of detail during acquisition based on particular events. It is not
uncommon to have an observed quantity that changes rapidly in time and than
last steady or possibly in a non interesting state for long periods. An
example of is the breakdown event that occurs in the accelerator grids of a
ion source, leading to a very fast transient change in the measured currents
and voltages of the grid power supply. In this case, fast data acquisition
must be triggered by the event itself, acquiring data for a short time window
around the event occurrence. This technique has been applied to Nio experiment
[12] a small radio frequency negative ions beam source with a high voltage
electrostatic particle accelerator stage composed of grids. In certain
conditions break-down events [14] appear on the high voltage gaps of the grids
causing a high current discharges of the power supply feeding the accelerator.
A subset of the FPGA functionality described in section 3 has been implemented
in a Red Pitaya device, namely the trigger logic to detect the occurrence of
the event, the pre and post trigger sampling logic and the FIFO/DMA data
transfer to computer memory via the GNU Linux driver. In this case data are
streamed and when an event is detected and data collected at 5 MHz sampling
speed along the corresponding time window, the data block is passed, either
via FIFO or DMA, to the linux driver and then, in turn, to a program in the
Zynq processor that communicates the newly acquired data block to the central
data acquisition system via TCP/IP. The results are displayed in Fig. 4,
showing the events acquired during a beam generation lasting 2 hours. Each
time window lasts 1 ms, and one enlarged event is displayed in the lower part
of Fig. 4.

Figure 4: figure example.

##  VI Conclusions

The architecture of a a new flexible ADC device has been presented, aiming at
reducing the number of actual ADC channels by integrating high speed transient
recording and data streaming for real-time plasma control. In addition the
same ADC will be used to acquire both magnetic fields and their time
derivatives, providing FPGA based digital integration for the derivation of
the former. This new architecture is foreseen to be applied at the RFX-mod2
experiment, providing a significant cost reduction in respect to the
duplication of devices for transient recording and streaming. Moreover,
performing digital integration in place of the analog one before ADC
conversion improves the quality of plasma control that can now rely on
original time derivative signals. The use of the ANACLETO framework proved to
be extremely useful in the development process and shortened quite a bit the
learning time for new developers.

## References

  * [1] P. Sonato, G. Chitarin, P. Zaccaria, F. Gnesotto, S. Ortolani, A. Buffa, M. Bagatin, W. Baker, S. D. Bello, P. Fiorentin, L. Grando, G. Marchiori, D. Marcuzzi, A. Masiello, S. Peruzzo, N. Pomaro, and G. Serianni, “Machine modification for active mhd control in rfx,” _Fusion Engineering and Design_ , vol. 66-68, pp. 161 – 168, 2003, 22nd Symposium on Fusion Technology. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0920379603001777
  * [2] S. Peruzzo, M. Bernardi, R. Cavazzana, S. D. Bello, M. D. Palma, L. Grando, E. Perin, R. Piovan, A. Rizzolo, F. Rossetto, D. Ruaro, M. Siragusa, P. Sonato, and L. Trevisan, “Detailed design of the rfx-mod2 machine load assembly,” _Fusion Engineering and Design_ , pp. –, 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S092037961830499X
  * [3] G. Marchiori, R. Cavazzana, P. Bettini, L. Grando, and S. Peruzzo, “Upgraded electromagnetic measurement system for rfx-mod,” _Fusion Engineering and Design_ , vol. 123, pp. 892 – 896, 2017, proceedings of the 29th Symposium on Fusion Technology (SOFT-29) Prague, Czech Republic, September 5-9, 2016. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0920379617303204
  * [4] N. Pomaro and F. Basso, “Transducers and signal conditioners of the rfx new magnetic measurement system,” _Fusion engineering and design_ , vol. 74, no. 1-4, pp. 721–726, 2005.
  * [5] “Evaluation of noise limits of a precision adc for direct digital signal integration,” _Review of Scientific Istruments_ , vol. submitted.
  * [6] M. Zuin, N. Vianello, M. Spolaore, V. Antoni, T. Bolzonella, R. Cavazzana, E. Martines, G. Serianni, and D. Terranova, “Current sheets during spontaneous reconnection in a current-carrying fusion plasma,” _Plasma Physics and Controlled Fusion_ , vol. 51, no. 3, p. 035012, 2009.
  * [7] P. Innocente, P. Zanca, M. Zuin, T. Bolzonella, and B. Zaniol, “Tearing modes transition from slow to fast rotation branch in the presence of magnetic feedback,” _Nuclear Fusion_ , vol. 54, no. 12, p. 122001, 2014.
  * [8] “Incaa - dio4 timing board.” [Online]. Available: http://www.incaacomputers.com/products/by-function/digital-io/dio4/
  * [9] “Stemlab - redpitaya.” [Online]. Available: https://www.redpitaya.com
  * [10] A. J. N. Batista, A. Neto, M. Correia, A. M. Fernandes, B. B. Carvalho, J. C. Fortunato, J. Sousa, C. A. F. Varandas, F. Sartori, and M. Jennison, “Atca control system hardware for the plasma vertical stabilization in the jet tokamak,” _IEEE Transactions on Nuclear Science_ , vol. 57, no. 2, pp. 583–588, April 2010.
  * [11] A. Rigoni, G. Manduchi, A. Luchetta, C. Taliercio, and T. Schröder, “A framework for the integration of the development process of linux fpga system on chip devices,” _Fusion Engineering and Design_ , vol. 128, pp. 122–125, 2018.
  * [12] M. D. Muri, M. Cavenago, G. Serianni, P. Veltri, M. Bigi, R. Pasqualotto, M. Barbisan, M. Recchia, B. Zaniol, T. Kulevoy, S. Petrenko, L. Baseggio, V. Cervaro, F. D. Agostini, L. Franchin, B. Laterza, A. Minarello, F. Rossetto, M. Sattin, and S. Zucchetti, “Installation and first operation of the negative ion optimization experiment,” _Fusion Engineering and Design_ , vol. 96-97, pp. 249 – 252, 2015, proceedings of the 28th Symposium On Fusion Technology (SOFT-28). [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0920379615301368
  * [13] B. Carvalho, A. Batista, M. Correia, A. Neto, H. Fernandes, B. Gonçalves, and J. Sousa, “Reconfigurable atca hardware for plasma control and data acquisition,” _Fusion Engineering and Design_ , vol. 85, no. 3-4, pp. 298–302, 2010.
  * [14] M. Recchia, M. Bigi, and M. Cavenago, “Conceptual design and circuit analyses for the power supplies of the nio1 experiment,” _Fusion Engineering and Design_ , vol. 86, no. 6, pp. 1545 – 1548, 2011, proceedings of the 26th Symposium of Fusion Technology (SOFT-26). [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0920379611004510