# Empowering Large Language Models to Set up a Knowledge Retrieval Indexer via
Self-Learning

Xiang Liang1, Simin Niu1,∗ Zhiyu Li2, Sensen Zhang1 Shichao Song1 Hanyu Wang1
Jiawei Yang1 Feiyu Xiong2 Bo Tang2 Chenyang Xi2
1Department of Computer Science, Renmin University of China 2Institute for
Advanced Algorithms Research, Shanghai, China The authors contribute
equally.Corresponding<EMAIL_ADDRESS>
###### Abstract

Retrieval-Augmented Generation (RAG) offers a cost-effective approach to
injecting real-time knowledge into large language models (LLMs). Nevertheless,
constructing and validating high-quality knowledge repositories require
considerable effort. We propose a pre-retrieval framework named Pseudo-Graph
Retrieval-Augmented Generation (PG-RAG), which conceptualizes LLMs as students
by providing them with abundant raw reading materials and encouraging them to
engage in autonomous reading to record factual information in their own words.
The resulting concise, well-organized mental indices are interconnected
through common topics or complementary facts to form a pseudo-graph database.
During the retrieval phase, PG-RAG mimics the human behavior in flipping
through notes, identifying fact paths and subsequently exploring the related
contexts. Adhering to the principle of the path taken by many is the best, it
integrates highly corroborated fact paths to provide a structured and refined
sub-graph assisting LLMs. We validated PG-RAG on three specialized question-
answering datasets. In single-document tasks, PG-RAG significantly
outperformed the current best baseline, KGP-LLaMA, across all key evaluation
metrics, with an average overall performance improvement of 11.6%.
Specifically, its BLEU score increased by approximately 14.3%, and the
$F1_{QE}$ metric improved by 23.7%. In multi-document scenarios, the average
metrics of PG-RAG were at least 2.35% higher than the best baseline. Notably,
the BLEU score and $F1_{QE}$ metric showed stable improvements of around 7.55%
and 12.75%, respectively. Our code: https://github.com/IAAR-Shanghai/PGRAG.

##  1 Introduction

Retrieval-Augmented Generation (RAG) has garnered significant attention for
its ability to integrate real-time knowledge into Large Language Models (LLMs)
[1-6]. Nevertheless, achieving this requires the elegant construction of an
efficient index [7, 8]. A well-designed index can significantly enhance
retrieval speed, ensuring that LLMs quickly access relevant background
knowledge, thereby reducing the delay in generating responses [9].
Additionally, it can effectively filter out irrelevant information, thereby
improving the relevance of the retrieved content and making the generated
results more accurate and valuable [10-12]. Constructing the index involves
handling large volumes of texts, and organizing and storing them presents a
challenge [13].

Traditional index construction methods typically segment texts into fixed
chunks, which are then embedded and constructed into a standard index [8, 14].
While this approach is straightforward to implement, it overlooks the global
context, potentially leading to incomplete information retrieval. To address
this, researchers have proposed various index structures that can be
categorized into three main types: (1) chains [7, 15]: retain context
information to ensure continuity and completeness of information. Common
implementations include overlapping chunks and progressively expanding chunks.
Overlapping chunks maintain sequential coherence of information, while
progressively expanding chunks provide more comprehensive context by initially
retrieving small chunks and then expanding to larger information blocks; (2)
trees [16, 17]: organize hierarchical relationships between text blocks by
summarizing similar blocks layer by layer, capturing structured information
within the document; (3) graphs [18]: represents complex relationships between
blocks by establishing similarity-based connections between text blocks.

Despite simplicity and generality, the indexing methods above have limitations
in knowledge representation capabilities. For example, KGP [18] attempts to
represent relationships between blocks, such as parallel relations and
sequential reasoning relations, using simple similarity measures to support
complex queries. Additionally, most of these methods are based on the blocks
themselves, making them susceptible to the influence of blocks containing
irrelevant content. To mitigate this, [19] indexes at the fine-grained
proposition level, ensuring that each proposition contains all necessary
context information from the text, thereby reducing the interference of
irrelevant information and improving the quality of knowledge. However, this
method lacks the construction of relations between knowledge points, thus
making complex reasoning difficult. Methods such as T-RAG, KG-RAG [10-12, 20]
attempt to construct indexes on high-quality entity trees or knowledge graphs
(KGs), providing context with high knowledge density and enhanced reasoning
capabilities. However, the extraction of entities and the construction of
relations are inherently challenging, and these methods often require preset
schemas, thereby limiting their generality. For example, in Figure 1, if the
preset relation in the KG is "effects", it may not handle semantically
consistent but differently expressed relations like "affects", even though
they are similar in meaning. We have summarized these RAG methods in Table 5.
For more detailed information, refer to Appendix D.

Figure 1: Motivation. Existing RAG suffers from several issues: (1) limited
retrieval granularity: Chain/Tree/Graph-RAG typically use a fixed granularity,
such as sentences. KG-RAG employs type-preset structures, such as entities and
triples; (2) restricted relationships: similarity is often utilized to
generalize various logical relations, and the relations in KGs necessitate
strict definitions.

To balance knowledge representation capabilities and generality, we adopted a
self-learning approach for LLMs to develop an efficient knowledge retrieval
indexer. Specifically, we treat LLMs as students, providing them with raw
reading materials and encouraging it to self-learn and create mind maps. By
reading these materials, LLMs organizes the knowledge within the documents,
establishing a hierarchical index which not only avoids noise but also conveys
meaning more clearly. Subsequently, we establish connections between similar
or complementary pieces of knowledge, allowing the index to span multiple
documents. During the knowledge retrieval phase, we first generate Key Points
(KPs) which are similar to [21] as pseudo-answers to assist the retriever in
exploring knowledge paths on the pseudo-graph. Simultaneously, we optimized
the step-by-step evaluation of nodes and path prediction during the depth-
first search (DFS) process. The designed pseudo-graph retrieval (PGR)
algorithm transfers the processes of exploration (walking) and evaluation
(discrimination) to efficient matrices, thereby accelerating the localization
of evidence. Finally, we assemble the most significant knowledge paths into a
structured context, which is then fed into LLMs along with the query to
generate the response. We highlight our contributions as follows:

  * •

Balancing Generalization and Knowledge-based Indexing Paradigm: Leveraging the
general learning capabilities of large language models (LLMs) to autonomously
organize document content, thereby creating hierarchical indexes, which
reduces preset limitations, internalizes external knowledge, and achieves
knowledge alignment.

  * •

Cross-document Knowledge Construction: Establishing cross-document knowledge
relationships by connecting concise and well-organized mental indexs based on
common or complementary contents, which enhances the organization and
accessibility of knowledge indexes, thereby improving the model’s ability to
handle complex queries.

  * •

Structured Supporting Evidence: Using LLMs to transform raw queries into KPs,
thereby stimulating the utilization of the model’s internal implicit
knowledge, which involves retrieving and integrating highly relevant knowledge
paths related to KPs, building a hierarchical context that can be directly
processed by the model without additional interpretation.

##  2 Method

Figure 2: Pseudo-Graph Construction Overview. (1) We first extract FCIs to
convert a text into loosely structured evidence entries and perform
consistency checks on FCIs. (2) We input the verified FCIs along with their MT
into LLMs to generate a mind map. (3) We perform knowledge fusion at the topic
and fact levels, constructing super nodes and cross-document links to form a
pseudo-graph.

###  2.1 Preliminaries

Pseudo-Graph. Similar to traditional graph definitions [22], let
$\mathcal{PG}=(\mathcal{M},V_{s},E_{s})$ represent the pseudo-graph composed
of mind maps $\mathcal{M}$ extracted from a set of documents $D$, along with
super nodes $V_{s}$ and super relations $E_{s}$. A mind map $M\in\mathcal{M}$
connects topic, routes, and facts through navigational lines, forming rich
inter-document relationships: (1) topic entities $V_{t}$ are the set of all
mind map topics, and the topic provide a clear starting point for organizing
information in the mind map. (2) fact entities $V_{f}$ offer detailed data or
descriptions directly related to the topic; (3) route entities $V_{r}$ serve
as intermediate information nodes between topic and fact entities, helping to
elucidate and guide the knowledge transfer paths; (4) navigational lines
$E_{r}$ express various logical relationships between entities, guiding the
flow of knowledge. The set of node features $X$ includes the characteristics
of all entities, with each feature $x_{i}\in X$ corresponding to the knowledge
content of node $v_{i}\in V_{t,r,f}$. For any given topic entity $v_{t}\in
V_{t}$, there is a corresponding mind map $M_{t}\in\mathcal{M}$, defined as
follows:

$M_{t}=\\{C_{t}^{i}\\}=\left\\{(v_{t},e_{r}^{1},v_{r}^{1},e_{r}^{2},v_{r}^{2},\ldots,e_{r}^{n},v_{r}^{n},e_{r}^{n+1},v_{f})\mid
e_{r}\in E_{r},v_{r}\in V_{r},v_{f}\in V_{f}\right\\},$ (1)

where $C_{t}^{i}$ represents fact paths, i.e., routing chains. Each fact path
starts from the topic entity $v_{t}$, passes through a series of route
entities $v_{r}^{i}$ connected by navigational lines $e_{r}^{i}$, and
eventually leads to the corresponding fact entity $v_{f}$. Moreover, the super
nodes $V_{s}$ consist of super-topic nodes $V_{st}$ and super-fact nodes
$V_{sf}$, connected by super relations $E_{s}$ between topic nodes $v_{t}$ or
fact nodes $v_{f}$. For example, $(v_{t}^{1},e_{s},v_{t}^{2}),e_{s}\in E_{s}$
indicates that topic $v_{t}^{1}$ and topic $v_{t}^{2}$ share a thematic
similarity, facilitating cross-document information integration and knowledge
discovery.

Knowledge Embedding Learning. Traditional RAG methods primarily adopt
independent embedding approaches [8, 14], lacking the modeling of
relationships between pieces of knowledge. We propose a node embedding
learning method based on fact paths, where the embedding vector
$\text{emb}(v_{i})$ of each node $v_{i}$ represents the concatenated fact
chain formed by the attributes of all nodes in the path from the starting
topic $v_{t}$ to the current node $v_{i}$:

$\text{emb}(v_{i})=\text{emb}(\text{concat}(x_{1},x_{2},\ldots,x_{i}))\mid
v_{i}\in\\{V_{t},V_{r},V_{f}\\},$ (2)

where $x_{i}$ is the attribute of $v_{i}$, i.e., the knowledge text, and
$\text{concat}(\cdot)$ represents the concatenation operation of the texts. In
this paper, we use spaces to concatenate different texts. The
$\text{emb}(\cdot)$ denotes the embedding process, and we use pre-trained
models sentence transformers [23] to capture the structured path information
formed by all informational nodes from the topic to the current node.

###  2.2 Problem Statement

Given a query $\vec{q}$, the generator models a conditional distribution
$p(\vec{o}|\vec{q})$ to generate an output response $\vec{o}$. To generate
knowledge-based responses, RAG first retrieves relevant knowledge contexts
$\mathcal{Z}$, and then generates the response $\vec{o}$ based on contexts
$\mathcal{Z}$. Ideally, the generator and the retriever should be jointly
optimized to find an optimal context $\mathcal{Z}$, i.e., maximizes the
probability $\max_{\mathcal{Z}}p(\mathcal{Z}|\vec{q})\cdot
p(\vec{o}|\vec{q},\mathcal{Z})$, where $p(\mathcal{Z}|\vec{q})$ and
$p(\vec{o}|\vec{q},\mathcal{Z})$ represent the probabilities of the retriever
and the generator, respectively. In practice, due to computational resource
constraints and optimization difficulties, we typically choose to optimize the
retriever separately to retrieve a sub-graph
$\mathcal{Z}\subseteq\mathcal{PG}$ composed of fact paths $c_{fp}\in C$, which
explicitly provide knowledge relevant to the current query $\vec{q}$.

###  2.3 Pseudo-Graph Construction

As shown in Figure 2, the construction of the pseudo-graph mainly involves
three core steps: (1) extraction and verification of fact-checking items
(FCIs), (2) generation of mind maps, i.e., organizing knowledge within a
single document, and (3) construction of inter-document knowledge
relationships.

Construction of Mind Maps. PG-RAG first transforms the original text
$\mathbf{d}_{orig}\in D$ into fact-checking texts
$\mathbf{d}_{fci}=[d_{fci}^{1},\ldots,d_{fci}^{n}]$ generated by LLMs. During
knowledge extraction, LLMs focus on identifying fact $d_{fci}^{i}$ that can
verify the original text. This targeted fact-checking extraction approach
concentrates on verifiable facts that can directly support or refute the
original statements, thereby minimizing misleading information due to missing
context or misinterpretations. FCIs may involve fine-grained numerals, dates,
and locations, but also include coarse-grained macro facts, such as viewpoints
or policy content. Compared to direct extraction, our pre-transformation
process retains facts more comprehensively. Next, we perform consistency
checks on the extracted FCIs using the evaluation function $f$ which combines
BERT-Score $f_{bs}$ and ROUGE-L $f_{rl}$ and define two thresholds,
$\theta_{bs}$ and $\theta_{rl}$, for them:

$f(\mathbf{d}_{orig},\mathbf{d}_{fci})=(f_{bs}(\mathbf{d}_{orig},\mathbf{d}_{fci})\geq\theta_{bs]})\land(f_{rl}(\mathbf{d}_{orig},\mathbf{d}_{fci})\geq\theta_{rl}),$
(3)

where $\land$ denotes the logical "and" operation. Then, we get the output as
follows:

$\mathbf{d}_{fci}\leftarrow\mathbf{d}_{fci}\cdot\mathbb{I}(f(\mathbf{d}_{orig},\mathbf{d}_{fci}))+\operatorname{<regenerate>}\cdot\mathbb{I}(\neg
f(\mathbf{d}_{orig},\mathbf{d}_{fci})),$ (4)

where $\mathbb{I}(\cdot)$ is the indicator function. Thus, if the evaluation
result of is true, the output fact-checking text $\mathbf{d}_{fci}$ passes the
verification; otherwise, the output is the instruction "<regenerate>" and the
fact extraction is performed again. We further use LLMs to perform the second
transformation on the verified FCIs to form a hierarchical mind map $M_{i}$
around the topic, i.e., $M_{i}=\text{LLM}(\mathbf{d}_{fci}^{i},x_{t}^{i}),$
where $x_{t}^{i}\in X$ is the attribute of the topic node $v_{t}^{i}\in
V_{t}$.

Establishment of Cross-Document Relationships. We integrated the collected
mind maps $\mathcal{M}$ by constructing clusters and linking knowledge,
thereby establishing cross-document associations to form a structured pseudo-
graph network. During the clustering phase, we first performed knowledge
embedding learning on the nodes and calculated the clustering score
$sim^{cluster}=\text{sim}(\text{emb}(v_{i}),\text{emb}(v_{j}))$. Based on the
similarity $sim^{cluster}$, the similar node sets were grouped into clusters,
with each cluster assigned a super node as a connection point. Specifically,
we set similarity thresholds of 0.92 and 0.98 for the topic nodes $V_{t}$ and
the fact nodes $V_{f}$, respectively. Only nodes exceeding the thresholds were
clustered together. Once clusters were formed, the originally isolated mind
maps $\mathcal{M}$ was connected through super nodes $V_{s}$, allowing similar
topics or complementary facts to be linked, thereby enhancing the navigability
and accessibility of the information within the network. The specific
algorithm details and the case of pseudo-graph generation are provided in
Appendices E and F, respectively.

###  2.4 Knowledge Recall via Pseudo-Graph Retrieval

Figure 3: Pseudo-Graph Walking Overview. (1) Query the pseudo-graph database
to locate seed topics. (2) Explore nodes linked to seed topics to form
candidate nodes. (3) Load ids and vectors of the candidate nodes into template
matrices (TMs). (4) Generate KPs to assist retrieval. (5) Get similarity
matrices (SMs) based on KPs and $\mathcal{PG}_{vector}$. (6) Select top fact
paths as seed nodes. (7) Create control matrices (CMs) to assess the
contribution value of candidate nodes to seed nodes. (8) Select boundaries to
determine the reachable area from seed nodes. (9) Set values within boundaries
to 1, generate pathway matrices (PM) for seed nodes. (10) Multiply CMs by PMs
to generate Staining Matrices (SMs), which indicate the contribution values of
candidate nodes accessible from seed nodes. Sum all SMs to produce an
Aggregate Matrix (AM), representing the overall contribution of candidate
nodes to query. Integrate the top rows (fact paths) from AM into structured
context $\mathcal{Z}$.

Template Matrices Preload. When humans search for information, they typically
use clear "clues" to guide their search in an orderly and purposeful manner.
Once these key points are identified, they further refine the evidence by
selecting the relevant context. Our PGR algorithm mirrors similar retrieval
logic. As shown in Figure 3, first, among broad topics $V_{t}$, we use
similarity to filter out seed topic nodes $V_{t}^{seed}\subset V_{t}$ that are
most relevant to the query. Then, by exploring topic nodes $V_{t}^{con}$
associated with them, we merge and obtain candidate topic nodes
$V_{t}^{candi}=\\{V_{t}^{seed}\cup V_{t}^{con}\\}$. Specifically, we achieve
topic walking through super-topic nodes $V_{st}$ to obtain related topic
nodes, i.e., $V_{t}^{con}\rightarrow V_{st}\leftarrow V_{t}^{seed}$.
Additionally, we perform fact walking through super-fact nodes $V_{sf}$ on
fact nodes $V_{f}^{seed}\stackrel{{\scriptstyle*}}{{\leftarrow}}V_{t}^{seed}$
connected to seed topics $V_{t}^{seed}$ to explore other possibly related
topics, i.e.,
$V_{t}^{con}\stackrel{{\scriptstyle*}}{{\rightarrow}}V_{f}^{con}\rightarrow
V_{sf}\leftarrow V_{f}^{seed}$. Within the defined range of topics
$V_{t}^{candi}\in V^{candi}$, where candidate nodes $V^{candi}$ include
candidate topics $V_{t}^{candi}$ itself and all nodes associated with it.
Then, we use Key Points (KPs) to locate the fact nodes $V_{f}^{top}\subset
V^{candi}$ with the top similarity in parallel, and select them as seed nodes
$V_{f}^{seed}$, due to the fact node encode the entire path content from topic
to fact. The generation prompt and explanations for KPs can be found in
Appendix F. Next, starting from seed nodes $V_{f}^{seed}$, we perform an
upward DFS to simulate the behavior of searching for context. We optimized the
natural selection of gradually performing DFS exploration from the seed nodes,
as each step’s decision depends on the previous step’s evaluation,
significantly increasing the total traversal time. In detail, we preloaded the
IDs required for walking and the vectors needed for evaluation into template
matrices (TMs) which are used for the parallel execution of importance
evaluation and selection of candidate nodes $V^{candi}$. Specifically, the ID
template matrix $\mathcal{PG}_{id}$ records the IDs of an entire path from the
root to the leaf in each row. The vector template matrix
$\mathcal{PG}_{vector}$ stores the knowledge embeddings at the corresponding
positions.

Pathway Matrix Generation. In TMs, tracing from leave (fact) to the root
(topic) can be achieved through reverse traversal, i.e., moving from the right
to the left of the row. To continue exploring reachable child node paths from
any parent node $v\in{V}_{t,r}$, one needs to find positions in the ID matrix
$\mathcal{PG}_{id}$ where the IDs match the parent node ID, i.e., the co-
parent node indices ${ind}_{cp}$. By traversing right from these positions,
one can find traversal paths from the parent node as follows:

${trvP}_{cp}=\\{\mathcal{PG}_{id}[i:k]\mid
k\geq{ind}_{cp}[1],\mathcal{PG}_{id}[i,k]\neq-1\\}.$ (5)

Concretely, in TM $\mathcal{PG}_{id}$, all traversal paths with the same
parent node appear in consecutive rows. Therefore, a DFS from any node
$v^{start}$ to a parent node $v^{end}$ can be transformed into determining the
boundaries of the consecutive rows containing the parent node $v^{end}$.
First, the indices of the co-parent nodes are determined as
${ind}_{cp}=\\{(i,j)\mid\mathcal{PG}_{id}[i,j]=\text{id}(v^{end})\\}.$ The
left boundary $bnd_{l}={ind}_{cp}[1]$ is defined by the column index of the
parent node. The top and bottom boundaries are defined by the starting and
ending row coordinates of the co-parent nodes:

$(bnd_{t},bnd_{b})=(\min(i),\max(i)\mid\mathcal{PG}_{id}[i,bnd_{l}]=\text{id}(v^{end})).$
(6)

Next, traverse right from these positions in parallel until IDs are not empty
to establish right boundary:

$bnd_{r}=\min\left\\{k\mid\mathcal{PG}_{id}[i,k]\neq-1,i\in[bnd_{t}:bnd_{b}]\right\\}.$
(7)

Then, set values within the region to 1 to construct a pathway matrix from a
seed node as follows:

$PM_{i,j}^{v^{seed}}=(bnd_{t}\leq i\leq bnd_{b})\land(bnd_{l}\leq j\leq
bnd_{r}).$ (8)

Control Matrix Generation. To provide comprehensive and detailed context for
high-quality seed nodes, we impose controls on candidate nodes. Specifically,
for each seed node $v^{seed}$, we calculate contribution values of candidate
nodes $V^{candi}$ to the seed node and generate a Control Matrix
$CM^{v^{seed}}$. By comparing the candidate node similarity ${sim}^{candi}$
with the seed node similarity ${sim}^{seed}$, we set three control conditions:
(1) support: when the similarity difference meets the support threshold
$\theta_{s}=0.03$, the contribution value is $1\cdot{sim}^{candi}$, indicating
that the current node highly supports the seed node in answering the query;
(2) fuzzy: when the difference only meets the fuzzy threshold
$\theta_{f}=0.05$, the contribution value is $0.5\cdot{sim}^{candi}$,
indicating that the current node somewhat supports the seed node; (3) reject:
the contribution value is 0.

Next, starting from seed node $v^{seed}$, we traverse to left, calculating and
recording node contributions in $CM^{v^{seed}}$ until reaching the left
boundary $bnd_{l}$ required for the PM where the contribution value changed
from 1 to 0. Then, starting from $bnd_{l}$, we traverse right in parallel for
other rows, calculating and recording the contributions in $CM^{v^{seed}}$,
stopping when we first encounter the contribution value 0, i.e., not expanding
subsequent child nodes, ultimately generating a Control Matrix
$CM^{v^{seed}}$.

Context Generation. For each query $q$, we concurrently obtain multiple sets
of Control Matrices $CM^{V^{seed}}$ and Pathway Matrices $PM^{V^{seed}}$,
starting from the seed nodes using the corresponding KPs. We perform element-
wise multiplication of these matrices to obtain the contribution values of
candidate nodes reachable from the seed nodes, known as Staining Matrices
(SMs). Next, we sum the SMs to form the Aggregate Matrix (AM), which records
total contribution values of candidate nodes for the query $q$, considering
multiple KPs. Finally, we select the rows (fact paths) with the top total
contribution values, integrate their texts into the structured context
$\mathcal{Z}$ into LLMs for response:

$\mathcal{Z}=\text{topK}({\sum}_{v^{seed}\in V^{seed}}CM^{v^{seed}}\odot
PM^{v^{seed}}).$ (9)

The complete process of PGR is shown in Algorithm 1.

Algorithm 1 Knowledge Recall via Pseudo-Graph Retrieval Algorithm.

1:A query vector $\vec{q}$, the ID template matrix $\mathcal{PG}_{id}$, and
the vector template matrix $\mathcal{PG}_{vector}$.

2:A structured context $\mathcal{Z}$.

3:Use LLMs to generate the corresponding key points $\\{\vec{q}_{KP}\\}$.

4:for each $\vec{q}_{KP}$ do

5: Compute the similarity matrix: $SM=\vec{q}_{KP}\odot\mathcal{PG}_{vector}.$

6: Select seed nodes $V^{seed}$ from $SM$.

7:for each seed node $v^{seed}$ do

8: Traverse left in $SM$ to calculate contribution values and find the left
boundary $bnd_{l}$.

9: From $bnd_{l}$, traverse right to calculate contribution values to form the
control matrix $CM^{v^{seed}}$.

10: Extract the path matrix $PM^{v^{seed}}$ from $\mathcal{PG}_{id}$ using
Eqs. 6, 7, and 8.

11:Compute $\mathcal{Z}$ using Eq. 9.

12:return The structured context $\mathcal{Z}$.

##  3 Experiment

Table 1: Performance (%) of different baselines. The best and runner-up are in
bold and underlined.

Method | 1-Document | 2-Document | 3-Document
---|---|---|---
Bleu | Rouge-L | BertScore | $F1_{QE}$ | Bleu | Rouge-L | BertScore | $F1_{QE}$ | Bleu | Rouge-L | BertScore | $F1_{QE}$
w/o RAG | 41.37 | 59.59 | 81.52 | 55.54 | 21.82 | 35.52 | 83.92 | 37.96 | 20.08 | 32.55 | 84.27 | 34.72
BM25 | 39.91 | 57.33 | 83.36 | 59.3 | 24.61 | 38.31 | 86.86 | 47.63 | 20.98 | 34.33 | 87.02 | 42.01
DPR | 39.76 | 57.24 | 83.81 | 60.41 | 22.75 | 37.25 | 87.16 | 48.87 | 21.05 | 35.04 | 87.81 | 45.18
Hybrid | 39.67 | 57.38 | 84.06 | 60.44 | 24.03 | 38.43 | 87.3 | 51.11 | 21.35 | 35.34 | 87.66 | 45.54
| Hybrid+Rerank
---
40.63 | 58.26 | 84.68 | 62.81 | 24.53 | 38.91 | 87.89 | 52.08 | 21.74 | 35.88 | 88.21 | 46.54
| Tree Traversal
---
39.25 | 57.14 | 83.21 | 59.22 | 23.08 | 38.25 | 87.83 | 47.03 | 21.01 | 34.72 | 87.28 | 43.51
| Collapsed Tree
---
39.74 | 57.50 | 83.37 | 60.02 | 23.17 | 37.76 | 86.94 | 46.41 | 21.14 | 34.52 | 87.15 | 43.46
| Graph-RAG
---
40.32 | 58.39 | 84.38 | 61.59 | 23.32 | 38.62 | 87.91 | 51.93 | 21.87 | 36.60 | 87.44 | 46.98
KGP-LLaMA | 41.47 | 58.72 | 85.36 | 63.81 | 25.53 | 40.88 | 87.39 | 52.37 | 22.63 | 36.16 | 88.02 | 47.10
| PG
---
47.94 | 64.46 | 87.46 | 69.61 | 27.98 | 40.85 | 86.90 | 50.87 | 25.08 | 36.86 | 86.98 | 49.57
| PG w. KPs
---
53.07 | 66.64 | 88.40 | 71.14 | 26.89 | 41.69 | 88.03 | 52.24 | 24.88 | 38.78 | 88.56 | 51.38
| PG-RAG
---
55.73 | 69.68 | 89.78 | 79.66 | 29.19 | 43.08 | 88.09 | 55.71 | 26.97 | 39.19 | 88.31 | 52.83

###  3.1 Datasets

In this experiment, we selected three Question Answering (QA) datasets from
the CRUD-RAG benchmark [24] to assess the performance of the RAG system in
knowledge-intensive applications. These datasets evaluate the model’s ability
to answer fact-based questions and its capacity to reason using information
from multiple documents: 1-Document QA focuses on fact-based question
answering, examining the model’s ability to precisely locate and extract
relevant information. 2-Document QA tests whether the model can utilize and
integrate information from two documents for reasoning. 3-Document QA involves
questions that require the model to simultaneously synthesize information from
three documents, further increasing the complexity of the task and demanding
deeper understanding and analytical skills from the model. See Appendix B for
more details.

###  3.2 Baselines and Metrics

We compared PG-RAG with a variety of advanced baseline methods: (1)
GPT-3.5-turbo [25]; (2) native RAG methods including BM25 [26], dense passage
retrieval (DPR) [23], hybrid retrieval [8], and hybrid retrieval with reranker
[27]; (3) and RAG methods such as tree traversal [17], collapsed tree
retrieval [17], Graph-RAG [28], and KGP [18]. More details in Appendix C.

In the experiments, two types of evaluation metrics are employed to assess the
quality of generated text. Firstly, the overall semantic similarity metrics,
including BLEU [29], ROUGE-L [30], and BertScore [31], evaluate how closely
the generated content $GM$ aligns with the reference content $GT$ in terms of
meaning and fluency. Secondly, the key information metric, RAGQuestEval [24],
assesses how effectively the generated content captures and presents the key
information from the reference content. Specifically, entities and noun
phrases are extracted from the reference text to form a set of question-answer
pairs $\\{(q,a)\\}$ using a question generator $Q_{G}(\cdot)$, where $q$
represents a subquery and $r$ the corresponding reference to verify whether
the generated text contains and accurately conveys the content of the
reference. We involved the $F1_{QE}$ measure, which considers both precision
and recall as follows:

$\operatorname{Prec}(GT,GM)=\frac{1}{\left|Q_{G}(GT)\right|}\sum_{(q,a)\in
Q_{G}(GT)}F1\left(Q_{A}(GM,q),a\right),$ (10)
$\operatorname{Recall}(GT,GM)=\frac{1}{\left|Q_{G}(GT)\right|}\sum_{(q,a)\in
Q_{G}(GT)}\mathbb{I}[Q_{A}(GM,q)\neq\operatorname{<Unanswerable>}].$ (11)

where $\mathbb{I}$ evaluates whether the response to a query $q$ is
"<Unanswerable>" or not.

###  3.3 Implementation Details

In all baseline methods, we follow the same RAG foundation settings as the
CRUD-RAG benchmark, dividing the document repository into fixed-size chunks
(128) and using a uniform embedding model (bge-base [23]) with a commonly used
context window of 8. GPT-3.5 serves as the baseline model for the experiments,
handling response generation and quality assessment. On this basis, we
incorporate the RAG optimization modules proposed by each method. See Appendix
C for more details.

###  3.4 Results

Overall Comparison. In Table 1, we compare the performance of our proposed PG-
RAG method with other baseline methods, yielding the following results:

(1) In terms of BERTScore and $F1_{QE}$ metrics, the performance of the basic
generative model lags behind that of methods using RAG. This is due to the
model’s knowledge base potentially being insufficient for such problems,
leading to the generation of hallucinatory answers or choosing to evade, such
as claiming, "I cannot provide news." The traditional RAG methods, integrating
BM25 keyword search and DPR’s deep semantic matching, can retrieve relevant
information from documents more effectively. Among these, methods with a
hybrid re-ranking mechanism perform the best within traditional RAG, as
additional re-ranking algorithms can optimize the results of initial
retrieval.

(2) Tree-based baseline methods perform poorly across the three tasks, despite
attempting to extract and summarize information from document blocks by
constructing summary trees and trying to balance the performance of fine-
grained (base blocks) and coarse-grained (summary) information retrieval
through high-matching collapsed blocks or top-down adaptive search recall
strategies. However, these baseline methods using the RAPTOR Cluster approach
underperform in the large dataset used in this experiment, directly impacting
the final results.

Figure 4: Comparison of the block and fact embedding distributions in 2D
space.

(3) The Graph-RAG and KGP, two graph-based RAG methods that navigate the graph
structure to recall evidence, outperform traditional RAG and tree-based RAG in
multi-document tasks. Specifically, Graph-RAG uses beam search, while KGP
relies on the reasoning capabilities of LLMs themselves, making adaptive
evidence selection that meets the relationship reasoning demands of complex
question answering. However, in single-document question answering, the
performance improvement of these graph-based RAG models over traditional RAG
is not significant due to the limited complexity and amount of information in
single-document tasks.

(4) Our PG-RAG method markedly surpasses all baselines in single-document
question answering tasks, attributable to our transformation of the base text
into a refined, well-structured, and highly coherent pseudo-graph structure.
By navigating precisely through the routing nodes of the pseudo-graph, PG-RAG
can focus on key information and effectively gather related context as a
supplement. In tasks characterized by information redundancy and complexity
across multiple documents, PG-RAG continues to demonstrate stable high
performance.

Table 2: Comparison of three fusion algorithms based on the number of chunks
to be fused, the number of clusters generated, and the average number of
documents per cluster in topic fusion.

Method | Chunks | Clusters |  | Docs/
---
Cluster
RAPTOR | 153,577 | 46 | 277
KNN | 153,577 | 3,877 | 2.69
Ours | 10,436 | 3,500 | 2.98

Comparative Analysis of Knowledge Construction Methods. Traditional RAG only
performs simple chunking before retrieval. In contrast, tree-based and graph-
based RAGs integrate these chunks through fusion algorithms, associating or
aggregating them, but their performance highly depends on the quality and
distribution of the initial segmentation. For instance, we segmented a dataset
involving QA on 3,199 topics covering 10,436 articles, resulting in 153,577
chunk embeddings. As shown in Figure 4, the embeddings obtained from our
factual segmentation method are more dispersed in the embedding space compared
to the original block embeddings, which benefits clustering. As shown in Table
2, RAPTOR Cluster uses the GMM [32] algorithm to learn the distribution of
embeddings awaiting clustering and adaptively determines the number of
clustering layers. However, in large datasets, particularly where embedding
distributions are concentrated, RAPTOR Cluster aggregates the 153,577 chunks
into only 46 classes at the first layer, causing each summary block to
aggregate information from nearly 227 documents, leading to overly abstract
and noisy summary nodes. Additionally, RAPTOR Cluster assigns the blocks to be
aggregated into a fixed number of learned clusters by setting thresholds. If
the threshold is set too high, it becomes difficult for blocks to adapt to the
clustering distribution, resulting in sparse connections between layers, and
the final effect might be similar to ordinary chunking. If the threshold is
too low, almost every block has a high probability of being integrated into
the upper summary blocks, forming a full connection, which increases the noise
in the relationships. Hence, the quality of the tree in RAPTOR Cluster is
highly sensitive to the dataset and threshold settings. Graph-based methods
mostly use KNN [33] for clustering. Here, we set the number of neighbors to 3,
as the QA dataset was originally constructed by aggregating topics and
selecting 1-3 documents from different topics to generate questions. We found
that using KNN resulted in 3,877 clusters, close to the dataset’s own
aggregation characteristics, but the fusion took too long, requiring nearly 5
hours with 20 threads set. Meanwhile, our method builds indices at the topic
and fact levels, classifying each node with the top nodes meeting the
threshold into one class, with a time complexity close to O(n). Searching for
top nodes on the index is fast, in a single-thread setting, our fusion time
was only 0.5 hours.

Table 3: Comparison of knowledge integration results using different RAG
methods.

Method |  | Refinement
---
Rate
| Knowledge
---
Density
| Compression
---
Ratio
Tree ($\theta=0.3$) | 31% $\sim$ 32% | $1.9\cdot 10^{6}$ | 0.99 $\sim$ 1
Tree ($\theta=0.5$) | 31% $\sim$ 32% | $1.55\cdot 10^{6}$ | 0.99 $\sim$ 1
Tree ($\theta=0.8$) | 31% $\sim$ 32% | $0.99\cdot 10^{6}$ | 0.99 $\sim$ 1
KNN-Graph | 31% | $4.88\cdot 10^{6}$ | 1
PG (ours) | 100% | $4.11\cdot 10^{6}$ | 2.64

Comparative Analysis of Knowledge Construction Results. As shown in Table 3,
it is clear that pseudo-graph generated post-fusion demonstrates excellent
performance in terms of both the refinement level and density of knowledge.
First, the graph comprises the highest number of nodes, each encapsulating
distinct knowledge quantities and adjusting its granularity commensurate with
the extent of the knowledge. Second, dense interconnections have been
established among knowledge entities, facilitating the representation of
various connection types reflective of the logical structure of knowledge. In
contrast to the high-density KNN-Graph that employs a singular metric for all
connections, our approach not only establishes essential links among knowledge
entities but also minimizes connections between superficially similar yet
fundamentally disparate knowledge pieces, thereby augmenting the quality.
Crucially, the original knowledge has been effectively refined and compressed,
achieving a compression ratio exceeding 2.5 times that of the original texts,
thereby enhancing spatial efficiency.

Figure 5: Comparison of matching ability between raw query and KPs.

Impact of Pseudo-Graph Retrieval. PGR locates seed nodes in the initial recall
sub-graph through KPs as evidence, which may be more powerful than using the
original query directly for recall. As shown in Figure 5, the distribution of
similarity between KPs and the final answer (text composed of evidence set) is
significantly higher than that between the original query and the final
answer. This is because these key points can more precisely reflect the query
intent, allowing for more direct location of relevant information when
matching data in the knowledge base. Furthermore, assuming there are $w$
candidate nodes, the complexity of performing a step-by-step DFS is $O(w)$
because each reachable node needs to be visited sequentially. In PGR, $w$ is
stored within an $m\times n=w$ matrix, requiring only 3 row traversals and 1
column traversal to complete the search. Hence, the complexity is $O(m+3n)$.
Since the tree depth $n$ is very small and the width $m$ is large, in
practical terms PGR outperforms DFS in terms of speed.

##  4 Conclusion

This paper proposes a pre-retrieval augmented generation method that
introduces a "refinement" step before the "indexing-retrieval-generation"
process, ensuring the accuracy of retrieved content from the outset. We
leverage the self-learning capabilities of LLMs to transform documents into
easily understandable and retrievable hierarchical indexes. This process
naturally filters out noise and enhances information readability. By
establishing connections between similar or complementary pieces of knowledge,
we enable the retriever to function across multiple documents. During the
knowledge retrieval phase, we use "pseudo-answers" to assist the retriever in
locating relevant information and perform walking in the matrices, thereby
achieving accurate and rapid knowledge localization. Finally, we assemble the
retrieved fact paths into a structured context, providing rich background
information for LLMs to generate knowledge-grounded responses.

## References

[1] Kandpal, N., Deng, H., Roberts, A., Wallace, E., & Raffel, C. (2023) Large
language models struggle to learn long-tail knowledge. In International
Conference on Machine Learning, volume 202, pp. 15696–15707.

[2] Zhang, Y., Li, Y., Cui, L., Cai, D., Liu, L., Fu, T., Huang, X., Zhao, E.,
Zhang, Y., Chen, Y., Wang, L., Luu, A.T., Bi, W., Shi, F., & Shi, S. (2023)
Siren’s song in the AI ocean: A survey on hallucination in large language
models. arXiv preprint arXiv:2309.01219.

[3] Yang, K., Swope, A.M., Gu, A., Chalamala, R., Song, P., Yu, S., Godil, S.,
Prenger, R.J., & Anandkumar, A. (2023) Leandojo: Theorem proving with
retrieval-augmented language models. In Advances in Neural Information
Processing Systems.

[4] Mao, Y., Dong, X., Xu, W., Gao, Y., Wei, B., & Zhang, Y. (2024) FIT-RAG:
black-box RAG with factual information and token reduction. arXiv preprint
arXiv:2403.14374.

[5] Yan, S-Q., Gu, J-C., Zhu, Y., & Ling, Z-H. (2024) Corrective retrieval
augmented generation. arXiv preprint arXiv:2401.15884.

[6] Liu, Y., Peng, X., Zhang, X., Liu, W., Yin, J., Cao, J., & Du, T. (2024)
RA-ISF: learning to answer and understand from retrieval augmentation via
iterative self-feedback. arXiv preprint arXiv:2403.06840.

[7] Langchain. (2023a) Parent document retriever.
https://python.langchain.com/v0.1/docs/modules/data_connection/retrievers/parent_document_retriever.

[8] Langchain. (2023b) Ensemble retriever.
https://python.langchain.com/v0.1/docs/modules/data_connection/retrievers/ensemble.

[9] Bratanič, T., & Neo4j GenAI Research. (2024) Parent document retriever.
https://neo4j.com/developer-blog/knowledge-graph-rag-application.

[10] Fatehkia, M., Lucas, J.K., & Chawla, S. (2024) T-RAG: lessons from the
LLM trenches. arXiv preprint arXiv:2402.07483.

[11] Soman, K., Rose, P.W., Morris, J.H., Akbas, R.E., Smith, B., Peetoom, B.,
Villouta-Reyes, C., Cerono, G., Shi, Y., Rizk-Jackson, A., Israni, S., Nelson,
C.A., Huang, S., & Baranzini, S.E. (2023) Biomedical knowledge graph-enhanced
prompt generation for large language models. arXiv preprint arXiv:2311.17330.

[12] Kang, M., Kwak, J.M., Baek, J., & Hwang, S.J. (2023) Knowledge graph-
augmented language models for knowledge-grounded dialogue generation. arXiv
preprint arXiv:2305.18846.

[13] Zhang, H., Wang, Y., Chen, Q., Chang, R., Zhang, T., Miao, Z., Hou, Y.,
Ding, Y., Miao, X., Wang, H., Pang, B., Zhan, Y., Sun, H., Deng, W., Zhang,
Q., Yang, F., Xie, X., Yang, M., & Cui, B. (2023) Model-enhanced vector index.
In Advances in Neural Information Processing Systems.

[14] Langchain. (2023c) Semantic chunking.
https://python.langchain.com/v0.1/docs/modules/data_connection/indexing.

[15] Berntson, A. (2023) Azure ai search: Outperforming vector search with
hybrid retrieval and ranking capabilities.
https://techcommunity.microsoft.com/t5/ai-azure-ai-services-blog/azure-ai-
search-outperforming-vector-search-with-hybrid/ba-p/3929167.

[16] Chen, H., Pasunuru, R., Weston, J., & Celikyilmaz, A. (2023) Walking down
the memory maze: Beyond context limit through interactive reading. arXiv
preprint arXiv:2310.05029.

[17] Sarthi, P., Abdullah, S., Tuli, A., Khanna, S., Goldie, A., & Manning,
C.D. (2024) RAPTOR: recursive abstractive processing for tree-organized
retrieval. arXiv preprint arXiv:2401.18059.

[18] Wang, Y., Lipka, N., Rossi, R.A., Siu, A.F., Zhang, R., & Derr, T. (2024)
Knowledge graph prompting for multi-document question answering. In Thirty-
Eighth AAAI Conference on Artificial Intelligence, pp. 19206–19214.

[19] Chen, T., Wang, H., Chen, S., Yu, W., Ma, K., Zhao, X., Zhang, H., & Yu,
D. (2023) Dense X retrieval: What retrieval granularity should we use? arXiv
preprint arXiv:2312.06648.

[20] Wen, Y., Wang, Z., & Sun, J. (2023) Mindmap: Knowledge graph prompting
sparks graph of thoughts in large language models. arXiv preprint
arXiv:2308.09729.

[21] Gao, L., Ma, X., Lin, J., & Callan, J. (2023) Precise zero-shot dense
retrieval without relevance labels. In Proceedings of the 61st Annual Meeting
of the Association for Computational Linguistics (Volume 1: Long Papers), pp.
1762–1777.

[22] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P.S. (2021) A
comprehensive survey on graph neural networks. IEEE Transactions on Neural
Networks and Learning Systems, 32(1), pp. 4–24.

[23] Reimers, N., & Gurevych, I. (2019) Sentence-bert: Sentence embeddings
using siamese bert-networks. In Proceedings of the 2019 Conference on
Empirical Methods in Natural Language Processing and the 9th International
Joint Conference on Natural Language Processing, pp. 3980–3990.

[24] Lyu, Y., Li, Z., Niu, S., Xiong, F., Tang, B., Wang, W., Wu, H., Liu, H.,
Xu, T., & Chen, E. (2024) CRUD-RAG: A comprehensive chinese benchmark for
retrieval-augmented generation of large language models. arXiv preprint
arXiv:2401.17043.

[25] Kalyan, K.S. (2023) A survey of GPT-3 family large language models
including chatgpt and GPT-4. arXiv preprint arXiv:2310.12321.

[26] Robertson, S.E., & Zaragoza, H. (2009) The probabilistic relevance
framework: BM25 and beyond. Found. Trends Inf. Retr., 3(4), pp. 333–389.

[27] FlagOpen. Flagembedding. https://github.com/FlagOpen/FlagEmbedding.

[28] NebulaGraph. (2024) Graph rag: Unleashing the power of knowledge graphs
with llm. https://medium.com/@nebulagraph/graph-rag-the-new-llm-stack-with-
knowledge-graphs-e1e902c504ed.

[29] Papineni, K., Roukos, S., Ward, T., & Zhu, W-J. (2002) Bleu: a method for
automatic evaluation of machine translation. In Proceedings of the 40th Annual
Meeting of the Association for Computational Linguistics, pp. 311–318.

[30] Lin, C-Y. (2004) ROUGE: A package

for automatic evaluation of summaries. In Text Summarization Branches Out, pp.
74–81. Barcelona, Spain: Association for Computational Linguistics.

[31] Zhang, T., Kishore, V., Wu, F., Weinberger, K.Q., & Artzi, Y. (2020)
Bertscore: Evaluating text generation with bert. In International Conference
on Learning Representations.

[32] Stauffer, C., & Grimson, W.E.L. (1999) Adaptive background mixture models
for real-time tracking. In Proceedings. 1999 IEEE Computer Society Conference
on Computer Vision and Pattern Recognition (Cat. No PR00149), volume 2, pp.
246–252 Vol. 2.

[33] Cover, T.M., & Hart, P.E. (1967) Nearest neighbor pattern classification.
IEEE Trans. Inf. Theory, 13(1), pp. 21–27.

[34] Guo, Z., Cheng, S., Wang, Y., Li, P., & Liu, Y. (2023) Prompt-guided
retrieval augmentation for non-knowledge-intensive tasks. In Findings of the
Association for Computational Linguistics, pp. 10896–10912.

[35] Asai, A., Wu, Z., Wang, Y., Sil, A., & Hajishirzi, H. (2023) Self-rag:
Learning to retrieve, generate, and critique through self-reflection. arXiv
preprint arXiv:2310.11511.

[36] Jeong, S., Baek, J., Cho, S., Hwang, S.J., & Park, J.C. (2024) Adaptive-
rag: Learning to adapt retrieval-augmented large language models through
question complexity. arXiv preprint arXiv:2403.14403.

[37] DataStax. (2024) How colbert helps developers overcome the limits of rag.
https://hackernoon.com/how-colbert-helps-developers-overcome-the-limits-of-
rag.

[38] McCormick, Z., Clark, J., & Goldin, J. (2024) sprag.
https://github.com/SuperpoweredAI/spRAG.

[39] Langchain. (2023d) Semantic chunking.
https://python.langchain.com/v0.1/docs/modules/data_connection/document_transformers/semantic-
chunker.

##  Appendix A Limitations

PG-RAG has three major limitations: First, if the text is particularly long,
LLMs may not be able to transform the extracted FCIs into a complete mind map
due to their limited context window. To address this for long texts, we can
pre-segment the text before PG construction to reduce the processing burden on
LLMs. Although this method is feasible, the choice of pre-segmentation
strategy can affect the organization of knowledge, and inappropriate
segmentation may lead to the loss of contextual information. Second, using
LLMs for knowledge extraction is not economical for large-scale data
scenarios, despite achieving satisfactory results. Therefore, further fine-
tuning of lightweight models as alternatives is necessary. Fortunately, our
two-stage extraction approach simplifies each step, allowing lightweight
models to handle them. For example, converting text into fact-checking items
is essentially a content rewriting process, while generating the mind map
involves organizing the rewritten content. This drives us to continue model
fine-tuning in future research. Third, our walking algorithm performs only a
simple exploration of the pseudo-graph, namely locating key points and walking
to recall the context, failing to fully utilize the rich relationships
contained in the pseudo-graph. For example, by leveraging the relationships
between cross-document knowledge, we can compress redundant knowledge and
merge complementary knowledge, effectively internalizing the information. Our
initial work has not addressed this aspect, and future research will focus on
designing walking algorithms to achieve knowledge pruning.

##  Appendix B Datasets

Table 4: The summary of QA datasets.

Dataset Name | Dataset Size | Case
---|---|---
| Question Answering
---
(1-document)
3,199 |  | Through observations with the Webb Space Telescope, researchers discovered the
---
presence of dust containing which element in galaxies less than a billion
years old,
and this finding challenges which hypothesis about the formation of cosmic
dust?
Question Answering (2-document) | 3,199 |  | In the first half of 2023, which was higher within Shanghai’ jurisdiction:
---
the non-performing loan ratio in the banking industry or the original
insurance payout expenditure in the insurance industry?
| How do the recent policy upgrades and service promotions by the State
---
Administration of Foreign Exchange specifically support the cross-border trade
and investment and financing of technology-based small and medium-sized
enterprises?
Question Answering (3-document) | 3,199 |  | In terms of ensuring food safety, what measures have the customs authorities, provincial
---
food safety committees, and local market supervision bureaus taken
respectively?
| In 2023, what adjustments did the domestic refined oil prices undergo, and
how were
---
these adjustments influenced by changes in international oil prices and
domestic policies?

In Table 4, we provide several question-answering cases across different
document types, totaling 3,199 entries per type.

  * •

Question Answering (1-document): includes questions that focus on fact-based
information extracted from a single document. The questions require precise
retrieval of specific details from the provided text.

  * •

Question Answering (2-document): contains questions that necessitate the
integration of information from two documents. The questions are designed to
assess the ability to synthesize and compare information from multiple sources
to arrive at a coherent answer.

  * •

Question Answering (3-document): involves questions that require the
extraction and synthesis of information from three documents. These questions
test the model’s capability to handle more complex queries, where relevant
data must be gathered from multiple documents to form a complete and accurate
response.

##  Appendix C Experiment Details

In this section, we summarize the key implementation details for each baseline
as follows:

  * •

GPT-3.5-turbo [25] directly processes the questions from QA datasets and
generates responses based solely on the input question without any external
knowledge or context. This baseline helps assess the model’s intrinsic ability
to understand and respond to queries.

  * •

BM25 [26] is a sparse retrieval model that calculates the lexical overlapping
score between the query and the text corpus. In our implementation, we divide
the text into blocks. BM25 evaluates these blocks and ranks them based on the
relevance scores. We then use the content from the top-8 blocks to answer the
query. This approach tests the model’s ability to retrieve relevant
information based on lexical matching.

  * •

Dense Passage Retrieval [23] uses a pre-trained language model bge-base to
embed text blocks. The query is also embedded using the same model, and the
cosine similarity between the query vector and the text block vectors is
computed. The top-8 blocks with the highest similarity scores are retrieved.
This method evaluates the model’s capability to find semantically relevant
information using dense vector representations.

  * •

Hybrid Retrieval [8] combines the strengths of BM25 and DPR by merging their
retrieval results. We first retrieve blocks using both BM25 and DPR, creating
a combined list of unique blocks. Each block is then scored using a Reciprocal
Rank Fusion (RRF) approach, which calculates a weighted score based on the
ranks from both retrieval methods. The blocks are sorted by these combined
scores to determine the final ranking. The top-8 blocks with the highest
similarity scores are retrieved. This hybrid approach leverages both lexical
and semantic matching to improve retrieval accuracy.

  * •

Hybrid Retrieval with Reranker [27] extends the hybrid retrieval method by
adding a re-ranking step using the embedding model. After retrieving blocks
using BM25 and DPR, we use the reranker model bge-rerank-base to further
refine the ranking of the top retrieved blocks. This reranker leverages
advanced embedding techniques to enhance the accuracy of the final results.
Then We choose the top-8 blocks as contexts.

  * •

Tree Traversal [17] starts at the root level of the summary tree and retrieves
the top-8 nodes at each level based on cosine similarity to the query vector.
At each level, it selects the top-8 nodes from the child nodes of the previous
level’s top-8 nodes. Finally, we choose the 8 nodes with the highest
similarity as the context. This hierarchical method ensures that the most
relevant nodes are progressively identified and refined as the traversal
proceeds through the tree structure.

  * •

Collapsed Tree Retrieval [17] flattens the tree structure into a single layer,
ignoring the hierarchical structure. It calculates the cosine similarity of
all nodes at all levels to the query vector and retrieves the top-8 nodes with
the highest similarity as the context. This approach simplifies the retrieval
process by treating the entire tree as a flat structure, allowing for more
efficient identification of relevant nodes.

  * •

Graph-RAG [28] uses KNN to cluster base blocks and constructs similarity links
between nodes within the same cluster. During retrieval, we employ beam search
with inner product as the scoring function to rank the blocks. Specifically,
we limit the search depth to 3, as answering questions in our QA dataset
typically requires up to 3 hops of reasoning. We set the number of blocks
retrieved at each hop to 8, 5, and 3, respectively, generating a total of 120
retrieval paths. Each node’s score along a path is the product of the scores
from the first hop to the current hop. We rank all candidate nodes and select
the top 8 as the final context.

  * •

KGP-LLaMA [18] employs the LLaMA-7B model to generate the next supporting
evidence and then selects neighboring nodes similar to this evidence as the
next nodes to visit. Other settings are consistent with those of Graph-RAG.

  * •

PG-RAG (Ours). To ensure the quality and accuracy of the generated text, we
set the similarity thresholds $\theta_{bs}$ and $\theta_{rl}$ at 0.85 and
0.75, respectively. This ensures that while compressing information, we retain
key knowledge and maintain semantic coherence. During the implementation of
the walking algorithm, we set empirical values of 0.03 and 0.05 for the
support threshold $\theta_{s}$ and the fuzzy threshold $\theta_{f}$. Setting
lower thresholds means we are more stringent in selecting candidate nodes,
thereby improving the accuracy of the final results. This method allows us to
precisely filter out the most relevant candidate nodes. Finally, we calculate
the total contribution value of all candidate paths and select the top 8 fact
paths with the highest total contribution values as our contextual
information. These paths are typically within 128 tokens in length, as the
content of the fact paths is closer to propositional expressions, making them
more concise than basic blocks.

Table 5: Rleated works

Method |  | Block
---
strategy
Block type | Data granularity | Data mode |  | Constraint
---
type
| Retrieval
---
dependency
Walk |  | Retrieval
---
evidence
RAG [8,34,37] | Standard | Invariant | Token/Sentence/Passage | Independent block | Hard | No | No |  | Independent
---
block
| RAG w.
---
overlap [15]
Standard | Incremental | Token/Sentence/Passage | Overlapping block | Hard | No | No |  | Independent
---
block
PDR [7] |  | Standard or
---
semantic
Incremental | Granularity not uniform | From small to large | Soft | Single | No |  | Chain tail
---
node
| spRAG [19, 38, 39]
---
Semantic | * | Granularity not uniform |  | Independent block/
---
Overlapping block
Soft | No or single | No |  | Independent
---
block
| MEMWALKER [16];
---
RAPTOR [17]
Semantic | Incremental |  | Block,
---
bolck summary
Nodes and links | Soft | Single | Yes |  | Tree
---
nodes
T-RAG [10] | Semantic | Compression | Entities and triples | Nodes and links | Hard | Single | No | Sub-tree
| KG-RAG [11];
---
SURGE [12]
Semantic | Compression | Entities and triples | Nodes and links | Hard | Preset | No | Sub-graph
Mindmap [20] | Semantic | Compression | Entities and triples | Nodes and links | Hard | Preset | Yes | Sub-graph
KGP [18] | Standard | Invariant |  | Block or
---
block structure
Nodes and links | Hard | Preset | Yes | Sub-graph
PG-RAG | Semantic | Compression |  | Topics, routes, facts,
---
fact paths, concepts, etc.
Nodes and links | Free | Various | Yes |  | Pseudo
---
Sub-graph

##  Appendix D Related Work

###  D.1 Index Construction for Efficient Information Retrieval

In the field of information retrieval, index construction is a crucial step
that directly impacts retrieval efficiency and accuracy. Traditional RAG
(Retrieval-Augmented Generation) strategies enhance retrieval efficiency
through different segmentation methods, such as ordinary segmentation and
semantic segmentation. Ordinary segmentation strategies include independent
blocks and overlapping blocks. Independent blocks divide data into fixed-size
blocks that have no relationship with each other, while overlapping blocks
allow overlap between blocks, increasing processing flexibility. These
segmentation methods fall under hard constraint RAG approaches, where data
patterns and granularity strictly adhere to predefined rules. In contrast,
semantic segmentation adapts to the semantic content of the text with
inconsistent granularity, falling under soft constraint RAG methods. It
relaxes granularity constraints but remains limited to independent or
overlapping blocks in most traditional RAG methods.

MEMWALKER and RAPTOR strategies extract and integrate paragraphs and paragraph
summaries, relaxing granularity constraints and using the tree structure
formed during integration for subsequent retrieval, falling under incremental
segmentation with significant resource overhead. T-RAG employs a compressed
segmentation strategy, extracting entities such as departments and
organizations and the subordinate relationships forming an entity tree. It
represents knowledge through nodes and showcases hierarchical and subordinate
relationships between entities through links, providing a structured
representation method for hierarchical information within organizations. When
responding to user queries, T-RAG not only retrieves text blocks from the
document database as context but also checks if the query mentions entities in
the entity tree, thereby offering more accurate and enriched answers.

KG-RAG, SURGE, and Mindmap strategies achieve semantic segmentation by
compressing data onto a structured knowledge graph. This hard constraint RAG
paradigm ensures data constraints and entity relationship formation patterns,
which are crucial for constructing accurate indexes and enhancing retrieval
efficiency. However, the construction difficulty is extremely high, making it
difficult to directly apply to new domain data. The KGP algorithm employs a
general knowledge graph construction method, combining hard segmentation and
similarity relationships to enhance the generalization ability of the
knowledge graph. It divides data into paragraph or document structure blocks
and calculates semantic similarity and keyword similarity between blocks to
establish similarity links, relaxing data constraints, but the expressive
capability of a single semantic similarity model is limited.

Our PG-RAG adopts an unconstrained semantic segmentation strategy, adaptively
dividing data into themes, routes, facts, fact paths, concepts, events, and
other granularities, allowing the construction of more dynamic and adaptable
indexes to handle more complex retrieval tasks. PG-RAG adaptively segments
according to knowledge granularity, and the relationships between nodes are
not limited to subordinate relationships. They can also include parallel
relationships, associative relationships, logical relationships,
classification relationships, and expansion relationships, which are
automatically determined based on the actual situation and needs of the data.
This diversification of node relationships in the index construction method
makes it more flexible and adaptable.

###  D.2 Evidence Retrieval Mechanisms in Information Retrieval

In the field of information retrieval, an effective evidence retrieval
mechanism is crucial for enhancing retrieval quality and efficiency.
Traditional Retrieval-Augmented Generation (RAG) strategies typically recall
the top few independent blocks with the highest similarity as evidence,
without leveraging relationships between blocks. RAG strategies based on
incremental data models additionally incorporate simple hierarchical
relationships between small and large blocks. During evidence retrieval, these
models return the tail node of the chain as evidence, providing more
comprehensive contextual information. Neither of these strategies involves
complex walking mechanisms for retrieval.

MEMWALKER, on the other hand, relies on similarity relationships between
summaries for contextual walking and retrieval. By using LLM-based agents, it
makes top-down decisions on the summary tree and recalls the specific
paragraphs pointed to by the summary chain that meet the requirements. This
shows that MEMWALKER can navigate through the tree structure via specific
paths to reach more detailed information points. RAPTOR employs both top-down
and folded-tree search strategies for evidence retrieval. T-RAG focuses on
specific branches within the tree structure to extract relevant information.
Specifically, T-RAG relies on subordinate relationships between entities
during retrieval, directly returning the sub-tree formed by the path
containing the required entities as evidence without performing additional
navigation to recall more contextual information.

RAG methods based on (KGs, such as KG-RAG, SURGE, and Mindmap, generally use
predefined relationships as retrieval dependencies. For example, KG-RAG
presets connections between entities such as genes, proteins, drugs,
compounds, and diseases. KG-RAG and SURGE perform sub-graph matching through
entity linking, while Mindmap further expands the context using path-based and
neighbor-based exploration strategies. Ultimately, these KG-based RAG methods
use the retrieved sub-graph structure as evidence to assist the large model in
response generation. Our PG-RAG relies on adaptively generated rich
relationships for the navigation and selection of evidence pseudo-graphs. This
strategy is not limited to predefined relationship models but instead utilizes
the inherent connections within the data itself for subsequent retrieval,
demonstrating strong adaptability.

##  Appendix E Knowledge Fusion Algorithm

Algorithm 2 Knowledge Fusion for Pseudo-Graph Generation

1:Mind maps $\mathcal{M}$, topic entities $V_{t}$, fact entities $V_{f}$.

2:A pseudo-graph $\mathcal{PG}$.

3:Initialize visited nodes set $visited\\_nodes\leftarrow\\{\\}$

4:for each $node=$ $v_{i}\in V_{i=t,f}$ do

5: if $node.ID\not\in visited\\_nodes$ then

6: $sim\\_nodes\leftarrow\text{findSimilarNodes}(node,V_{i})$

7: $super\\_node\leftarrow\text{createSuperNode}(sim\\_nodes)$

8: $\mathcal{PG}.\text{addEdge}(sim\\_nodes,\text{link},super\\_node)$

9: $visited\\_nodes.\text{add}(sim\\_nodes.ID)$

10:return $\mathcal{PG}$

Algorithm 2 outlines the knowledge fusion algorithm used for pseudo-graph
generation. It accepts a collection of mind maps as input, comprising various
topics, routes, and fact nodes, with topic nodes represented by topic vectors
and fact nodes by path vectors. The algorithm begins by initializing two
collections: one for storing the final cluster results and another for
tracking visited and processed nodes. Subsequently, it commences a general
processing sequence, traversing nodes of both topic and fact types. For each
type of node, the algorithm verifies whether it has been visited. If not, it
selects the appropriate vector set based on the node type, either the topic
vector set $T_{v}$ or the fact path vector set $P_{v}$ and conducts a search
for similar nodes. The function findSimilarNodes, which calculates similarity
based on the node’s vector and its comparison with other vectors in the vector
set, identifies nodes that exceed a specific threshold. After identifying
these similar nodes, the algorithm generates a new super-node that represents
a group of closely related similar nodes. Subsequently, it establishes an edge
labeled as a similarity link between each identified similar node and the
newly generated super-node. These links demonstrate that these nodes are
similar in content and are now affiliated with a common super-node. The IDs of
each identified similar node are added to the $visited\\_nodes$ collection,
signifying that they have been processed. Meanwhile, the ID of the current
node and its associated super-node are incorporated into the Clusters cluster
collection. This process is executed identically for both topic and fact
nodes. Finally, upon processing all nodes, the algorithm returns the
constructed pseudo-graph PG. The constructed pseudo-graph PG not only aids in
maintaining the organization of information but also enhances the
intuitiveness and speed of information retrieval. Users can rapidly grasp the
core content of specific clusters by exploring these super-nodes and further
navigate to related detailed information through these nodes.

##  Appendix F Case Study

In Figures 6 and 7, we demonstrate the two-stage knowledge extraction process.
Figure 1 shows that through pre-extraction of knowledge, we can preliminarily
organize the information. Then, a mind map index is generated, which is
concise, hierarchical, and effectively compresses the knowledge. Furthermore,
we generate key answer points for queries. Specifically, we prompt the LLMs:
"Please provide a concise and accurate answer key, listing the key or specific
information needed to answer this question as comprehensively as possible."
For instance, for a simple factual question like "What is the trend of dry eye
occurrence?", the answer key would be "The trend of dry eye occurrence is
increasing or decreasing." We retrieve similar information from a high-quality
knowledge base, and if the fact indicates an increase, the answer trend will
be increasing, and vice versa. For complex queries involving multiple answer
points, such as "What environmental factors might exacerbate children’s dry
eye symptoms?", the model generates answer points from multiple perspectives,
such as screen time and indoor air quality. We can concurrently locate
relevant knowledge in the knowledge base, ensuring the breadth of the answer.
Additionally, to enhance the depth of the answer, we perform PGR (Pseudo-Graph
Retrieval) walks in the knowledge base to gather useful context. For example,
for the question "What flood control measures has Beijing implemented?", we
can locate the seed node, i.e., the fact path "Beijing -> flood control
measures -> work stoppage", and then find the routing node "flood control
measures" upwards to supplement more comprehensive knowledge. For more
detailed questions like "What is the difference between work stoppage and
production stoppage in flood control measures?", the fact path "Beijing ->
flood control measures -> production stoppage" has a higher support
probability than the fact path "Beijing -> flood control measures -> class
suspension" and is used as a seed node to supplement knowledge, supporting the
answer to the question.

Figure 6: A specific case of main topic and fact-checking items.  Figure 7: A
specific case of the mind map generated through main topic and fact-checking
items.


# A Fully Quaternion-Valued Capon Beamformer Based on Crossed-Dipole Arrays

Xiang Lan and Wei Liu
Communications Research Group
Department of Electronic and Electrical Engineering
University of Sheffield, UK

###### Abstract

Quaternion models have been developed for both direction of arrival estimation
and beamforming based on crossed-dipole arrays in the past. However, for
almost all the models, especially for adaptive beamforming, the desired signal
is still complex-valued and one example is the quaternion-Capon beamformer.
However, since the complex-valued desired signal only has two components,
while there are four components in a quaternion, only two components of the
quaternion-valued beamformer output are used and the remaining two are simply
removed. This leads to significant redundancy in its implementation. In this
work, we consider a quaternion-valued desired signal and develop a full
quaternion-valued Capon beamformer, which has a better performance and a much
lower complexity and is shown to be more robust against array pointing errors.

Keywords — quaternion model, crossed-dipole, Capon beamformer, vector sensor
array.

##  I Introduction

Electromagnetic (EM) vector sensor arrays can track the direction of arrival
(DOA) of impinging signals as well as their polarization. A crossed-dipole
sensor array, firstly introduced in [1] for adaptive beamforming, works by
processing the received signals with a long polarization vector. Based on such
a model, the beamforming problem is studied in detail in terms of output
signal-to-interference-plus-noise ratio (SINR) [2]. In [3, 4], further
detailed analysis was performed showing that the output SINR is affected by
DOA and polarization differences.

Since there are four components for each vector sensor output in a crossed-
dipole array, a quaternion model instead of long vectors has been adopted in
the past for both adaptive beamforming and direction of arrival (DOA)
estimation [5, 6, 7, 8, 9]. In [10], the well-known Capon beamformer was
extended to the quaternion domain and a quaternion-valued Capon (Q-Capon)
beamformer was proposed with the corresponding optimum solution derived.

However, in most of the beamforming studies, the signal of interest (SOI) is
still complex-valued, i.e. with only two components: in-phase (I) and
quadrature (Q). Since the output of a quaternion-valued beamformer is also
quaternion-valued, only two components of the quaternion are used to recover
the SOI, which leads to redundancy in both calculation and data storage.
However, with the development of quaternion-valued wireless communications
[11, 12, 13], it is very likely that in the future we will have quaternion-
valued signals as the SOI, where two traditional complex-valued signals with
different polarisations arrive at the array with the same DOA. In such a case,
a full quaternion-valued array model is needed to compactly represent the
four-component desired signal and also make sure the four components of the
quaternion-valued output of the beamformer are fully utilised. In this work,
we develop such a model and propose a new quaternion-valued Capon beamformer,
where both its input and output are quaternion-valued.

This paper is structured as follows. The full quaternion-valued array model is
introduced in Section II and the proposed quaternion-valued Capon beamformer
is developed in Section III. Simulation results are presented in IV, and
conclusions are drawn in Section V.

##  II Quaternion model for array processing

A quaternion is constructed by four components [14, 15], with one real part
and three imaginary parts, which is defined as $q=q_{a}+iq_{b}+jq_{c}+kq_{d}$,
where $i,j,k$ are three different imaginary units and
$q_{a},q_{b},q_{c},q_{d}$ are real-valued. The multiplication principle among
such units is

$i^{2}=j^{2}=k^{2}=ijk=-1,$ (1)

and

$ij=-ji=k,ki=-ik=j,jk=-ki=i$ (2)

The conjugate $q^{*}$ of $q$ is $q^{*}=q_{a}-iq_{b}-jq_{c}-kq_{d}$.

A quaternion number can be conveniently denoted as a combination of two
complex numbers $q=c_{1}+ic_{2}$, where the complex number
$c_{1}=q_{a}+jq_{c}$ and $c_{2}=q_{b}+jq_{d}$. We will use this form later to
represent our quaternion-valued signal of interest.

Consider a uniform linear array with $N$ crossed-dipole sensors, as shown in
Fig. 1, where the adjacent vector sensor spacing $d$ equals half wavelength,
and the two components of each crossed-dipole are parallel to $x-$ and
$y-$axes, respectively. A quaternion-valued narrowband signal $s_{0}(t)$
impinges upon the vector sensor array among other $M$ uncorrelated quaternion-
valued interfering signals $\\{s_{m}(t)\\}_{m=1}^{M}$, with background noise
$n(t)$. $s_{0}(t)$ can be decomposed into

$s_{0}(t)=s_{01}(t)+is_{02}(t)\;,$ (3)

where $s_{01}(t)$ and $s_{02}(t)$ are two complex-valued sub-signals with the
same DOA but different polarizations.

Assume that all signals are ellipse-polarized. The parameters, including DOA
and polarization of the $m$-th signal are denoted by
$(\theta_{m},\phi_{m},\gamma_{m1},\eta_{m1})$ for the first sub-signal and
$(\theta_{m},\phi_{m},\gamma_{m2},\eta_{m2})$ for the second sub-signal. Each
crossed-dipole sensor receives signals both in the $x$ and $y$ sub-arrays.

Figure 1: A crossed-dipole linear array with $N$ vector sensors.

For signal $s_{m}(t)$, the corresponding received signals at the $x$ and $y$
sub-arrays are respectively given by [16]:

$\displaystyle\emph{{x}}(t)=\emph{{a}}_{m1}p_{xm1}s_{m1}(t)+\emph{{a}}_{m2}p_{xm2}s_{m2}(t)$
$\displaystyle\emph{{y}}(t)=\emph{{a}}_{m1}p_{ym1}s_{m1}(t)+\emph{{a}}_{m2}p_{ym2}s_{m2}(t)$
(4)

where $\emph{{x}}(t)$ represents the received part in the x-sub-array,
$\emph{{y}}(t)$ represents the part in the y-sub-array, and
$(p_{xm1},p_{ym1})$ and $(p_{xm2},p_{ym2})$ are the polarizations of the two
complex sub-signals in $x$ and $y$ directions, respectively, which are given
by [17],

$\displaystyle p_{xm1}$ $\displaystyle=-\cos{\gamma_{m1}}$ (5) $\displaystyle
p_{ym1}$ $\displaystyle=\cos{\phi_{m}}\sin{\gamma_{m1}}{e}^{j\eta_{m1}}$
$\displaystyle p_{xm2}$ $\displaystyle=-\cos{\gamma_{m2}}$ $\displaystyle
p_{ym2}$
$\displaystyle=\cos{\phi_{m}}\sin{\gamma_{m2}}{e}^{j\eta_{m2}},\quad\text{when}\quad\theta_{m}=\frac{\pi}{2}$

Note that $\emph{{a}}_{m1}$ and $\emph{{a}}_{m2}$ are the steering vectors for
the two sub-signals, which are equal to each other since the two sub-signals
share the same DOA $(\theta_{m},\phi_{m})$.

$\displaystyle\emph{{a}}_{m1}=[1\quad
e^{\frac{-j2\pi\sin{\theta_{m}}\sin{\phi_{m}}}{\lambda}},...e^{\frac{-j(N-1)2\pi\sin{\theta_{m}}\sin{\phi_{m}}}{\lambda}}]^{\text{T}}$
$\displaystyle\emph{{a}}_{m2}=[1\quad
e^{\frac{-j2\pi\sin{\theta_{m}}\sin{\phi_{m}}}{\lambda}},...e^{\frac{-j(N-1)2\pi\sin{\theta_{m}}\sin{\phi_{m}}}{\lambda}}]^{\text{T}}$
(6)

A quaternion model can be constructed by combining the two parts as below:

$\displaystyle\emph{{q}}_{m}(t)$ $\displaystyle=\emph{{x}}(t)+i\emph{{y}}(t)$
(8) $\displaystyle=\emph{{a}}_{m1}(p_{xm1}+ip_{ym1})s_{m1}(t)$
$\displaystyle+\emph{{a}}_{m2}(p_{xm2}+ip_{ym2})s_{m2}(t)$
$\displaystyle=\emph{{b}}_{m1}s_{m1}(t)+\emph{{b}}_{m2}s_{m2}(t)$

where $\\{\emph{{b}}_{m1},\emph{{b}}_{m2}\\}\in\mathbb{H}^{N\times 1}$ can be
considered as the composite quaternion-valued steering vector. Combining all
source signals and the noise together, the result is given by:

$\emph{{q}}(t)=\sum\limits^{M}_{m=0}(\emph{{b}}_{m1}s_{m1}(t)+\emph{{b}}_{m2}s_{m2}(t))+\emph{{n}}_{q}(t)$
(9)

where $\emph{{n}}_{q}(t)=\emph{{n}}_{x}(t)+i\emph{{n}}_{y}(t)$ is the
quaternion-valued noise vector consisting of the two sub-array noise vectors
$\emph{{n}}_{x}(t)$ and $\emph{{n}}_{y}(t)$.

##  III Full quaternion Capon beamformer

###  III-A The Full Q-Capon Beamformer

To recover the SOI among interfering signals and noise, the basic idea is to
keep a unity response to the SOI at the beamformer output and then reduce the
power/variance of the output as much as possible [18, 19]. The key to
construct such a Capon beamformer in the quaternion domain is to design an
appropriate constraint to make sure the quaternion-valued SOI can pass through
the beamformer with the desired unity response.

Again note that the quaternion-valued SOI can be expressed as a combination of
two complex sub-signals. To construct such a constraint, one choice is to make
sure the first complex sub-signal of the SOI pass through the beamformer and
appear in the real and $j$ components of the beamformer output, while the
second complex sub-signal appear in the $i$ and $k$ components of the
beamformer output. Then, with a quaternion-valued weight vector _w_ , the
constraint can be formulated as

$\emph{{w}}^{\text{H}}\emph{{C}}=\emph{{f}}$ (10)

where $\\{\\}^{\text{H}}$ is the Hermitian transpose (combination of the
quaternion-valued conjugate and transpose operation),
$\emph{{C}}=[\emph{{b}}_{01}\quad\emph{{b}}_{02}]$, and $\emph{{f}}=[1\quad
i]$.

With this constraint, the beamformer output $z(t)$ is given by

$\displaystyle z(t)$ $\displaystyle=\emph{{w}}^{\text{H}}\emph{{q}}(t)$ (11)
$\displaystyle=\underbrace{s_{01}(t)+is_{02}(t)}_{s_{0}(t)}+\emph{{w}}^{\text{H}}\emph{{n}}_{q}(t)$
$\displaystyle\quad+\sum\limits^{M}_{m=1}\emph{{w}}^{\text{H}}[\emph{{b}}_{m1}s_{m1}(t)+\emph{{b}}_{m2}s_{m2}(t)]$

Clearly, the quaternion-valued SOI has been preserved at the output with the
desired unity response.

Now, the full-quaternion Capon (full Q-Capon) beamformer can be formulated as

$\displaystyle\min$
$\displaystyle\emph{{w}}^{\text{H}}\emph{{R}}\emph{{w}}\text{ subject to
}\emph{{w}}^{\text{H}}\emph{{C}}=\emph{{f}}$ (12)

where

$\emph{{R}}=E\\{\emph{{q}}(t)\emph{{q}}^{\text{H}}(t)\\}\;.$ (13)

Applying the Lagrange multiplier method, we have

$l(\emph{{w}},\boldsymbol{\lambda})=\emph{{w}}^{\text{H}}\emph{{R}}\emph{{w}}+(\emph{{w}}^{\text{H}}\emph{{C}}-\emph{{f}})\boldsymbol{\lambda}^{\text{H}}+\boldsymbol{\lambda}(\emph{{C}}^{\text{H}}\emph{{w}}-\emph{{f}}^{\text{H}})$
(14)

where $\boldsymbol{\lambda}$ is a quaternion-valued vector.

The minimum can be obtained by setting the gradient of (14) with respect to
$\emph{{w}}^{*}$ equal to a zero vector [20]. It is given by

$\nabla_{\emph{{w}}^{*}}l(\emph{{w}},\boldsymbol{\lambda})=\frac{1}{2}\emph{{R}}\emph{{w}}+\frac{1}{2}\emph{{C}}\boldsymbol{\lambda}^{\text{H}}=\emph{{0}}$
(15)

Considering all the constraints above, we obtain the optimum weight vector
$\emph{{w}}_{opt}$ as follows

$\emph{{w}}_{opt}=\emph{{R}}^{-1}\emph{{C}}(\emph{{C}}^{\text{H}}\emph{{R}}^{-1}\emph{{C}})^{-1}\emph{{f}}^{\text{H}}\;.$
(16)

A detailed derivation for the quaternion-valued optimum weight vector can be
found at the Appendix.

In the next subsection, we give a brief analysis to show that by this optimum
weight vector, the interference part at the beamformer output $z(t)$ in (11)
has been suppressed effectively.

###  III-B Interference Suppression

Expanding the covariance matrix, we have

$\emph{{R}}=E\\{\emph{{q}}(t)\emph{{q}}^{\text{H}}(t)\\}=\emph{{R}}_{i+n}+\sigma^{2}_{1}\emph{{b}}_{01}\emph{{b}}_{01}^{H}+\sigma^{2}_{2}\emph{{b}}_{02}\emph{{b}}_{02}^{\text{H}}$
(17)

where $\sigma^{2}_{1},\sigma^{2}_{2}$ are the power of the two sub-signals of
SOI and $\emph{{R}}_{i+n}$ denotes the covariance matrix of interferences plus
noise. Using the Sherman-Morrison formula, we then have

$\emph{{w}}_{opt}=\emph{{R}}_{i+n}^{-1}\emph{{C}}\boldsymbol{\beta}$ (18)

where
$\boldsymbol{\beta}=(\emph{{C}}^{\text{H}}\emph{{R}}_{i+n}\emph{{C}})^{-1}\emph{{f}}^{\text{H}}\in\mathbb{H}^{2\times
1}$ is a quaternion vector.

Applying left eigendecomposition for quaternion matrix [21, 22, 23],

$\emph{{R}}_{i+n}=\sum\limits^{N}_{n=1}\alpha_{n}\emph{{u}}_{n}\emph{{u}}_{n}^{\text{H}}$
(19)

with
$\alpha_{1}\geq\text{...}\geq\alpha_{M-2}\textgreater{\alpha_{M-1}}=\text{...}=\alpha_{N}=2\sigma^{2}_{0}\in\mathbb{R}$,
where $2\sigma^{2}_{0}$ denotes the noise power.

With sufficiently high interference to noise ratio (INR), the inverse of
$\emph{{R}}_{i+n}$ can be approximated by

$\emph{{R}}_{i+n}^{-1}\approx\sum\limits^{N}_{n=M+1}\frac{1}{2\sigma^{2}_{0}}\emph{{u}}_{n}\emph{{u}}_{n}^{\text{H}}$
(20)

Then, we have

$\displaystyle\emph{{w}}_{opt}$
$\displaystyle=\sum\limits^{N}_{n=M+1}\frac{1}{2\sigma^{2}_{0}}\emph{{u}}_{n}\emph{{u}}_{n}^{\text{H}}\emph{{C}}\boldsymbol{\beta}=\sum\limits^{N}_{n=M+1}\emph{{u}}_{n}\rho_{n}$
(21)

where $\rho_{n}$ is a quaternion-valued constant. Clearly, $\emph{{w}}_{opt}$
is the right linear combination of $\\{u_{M+1},u_{M+2},\text{...},u_{N}\\}$,
and $\emph{{w}}\in\text{$span_{R}$}\\{u_{M+1},u_{M+2},\text{...},u_{N}\\}$.

For those $M$ interfering signals, their quaternion steering vectors belong to
the space right-spanned by the related $M$ eigenvectors, i.e.
$\emph{{b}}_{m1},\emph{{b}}_{m2}\in\text{$span_{R}$}\\{u_{1},u_{2},\text{...},u_{M}\\}$.
As a result,

$\displaystyle\emph{{w}}_{opt}^{\text{H}}\emph{{b}}_{m1}\approx
0,\emph{{w}}_{opt}^{\text{H}}\emph{{b}}_{m2}\approx 0,m=1,4,\text{...},M$ (22)

which shows that the beamformer has eliminated the interferences effectively.

###  III-C Complexity Analysis

In this section, we make a comparison of the computation complexity between
the Q-Capon beamformer in [10] and our proposed full Q-Capon beamformer. To
deal with a quaternion-valued signal, the Q-Capon beamformer has to process
the two complex sub-signals separately to recover the desired signal
completely, which means we need to apply the beamformer twice for a
quaternion-valued SOI. However, for the full Q-Capon beamformer, the SOI is
recovered directly by applying the beamformer once.

For the Q-Capon beamformer, the weight vector is calculated by
$\textbf{w}=\emph{{R}}^{-1}\emph{{a}}_{0}(\emph{{a}}_{0}^{\text{H}}\emph{{R}}^{-1}\emph{{a}}_{0})^{-1}$,
where $\textbf{a}_{0}$ is the steering vector for the complex-valued SOI. As
an example, we use Gaussian elimination to calculate the matrix inversion
$\emph{{R}}^{-1}$ and $\frac{1}{3}(N^{3}-N)$ quaternion-valued multiplications
are needed, equivalent to $\frac{16}{3}(N^{3}-N)$ real-valued multiplications.
Additionally, $\emph{{R}}^{-1}\emph{{a}}_{0}$ requires $16N^{2}$ real-valued
multiplications, while $16(N^{2}+N)$ real multiplications are needed for
$(\emph{{a}}_{0}^{\text{H}}\emph{{R}}^{-1}\emph{{a}}_{0})^{-1}$. In total,
$\frac{16}{3}N^{3}+32N^{2}+\frac{80}{3}N$ real multiplications are needed.
When processing a quaternion-valued signal, this number will be doubled and
the total number of real multiplications becomes
$\frac{32}{3}N^{3}+64N^{2}+\frac{160}{3}N$.

For the proposed full Q-Capon beamformer, in addition to calculating
$\emph{{R}}^{-1}$, $32N^{2}$ real multiplications are required to calculate
$\emph{{R}}^{-1}\emph{{C}}$ and $32M^{2}+32M+96$ real multiplications for
$(\emph{{C}}^{\text{H}}\emph{{R}}^{-1}\emph{{C}}_{0})^{-1}\emph{{f}}$. In
total, the number of real-valued multiplications is
$\frac{16}{3}M^{3}+64M^{2}+\frac{272}{3}M+96$, which is roughly half of that
of the Q-Capon beamformer.

##  IV Simulations Results

In our simulations, we consider $10$ pairs of cross-dipoles with half wave-
length spacing. All signals are assumed to arrive from the same plane of
$\theta=90\degree$ and all interferences have the same polarization parameter
$\gamma=60\degree$. For the SOI, the two sub-signals are set to (90°, 1.5°,
90°, 45°) and (90°, 1.5°, 0°, 0°), with inferences coming from (90°, 30°, 60°,
-80°), (90°, -70°, 60°, 30°), (90°, -20°, 60°, 70°), (90°, 50°, 60°, -50°),
respectively. The background noise is zero-mean quaternion-valued Gaussian.
The power of SOI and all interfering signals are set equal and SNR (INR) is
20dB.

Figure 2: The resultant beam pattern with $\theta=90\degree$ and
$\gamma=60\degree$.

Fig. 2 shows the resultant 3-D beam pattern by the proposed beamformer, where
the interfering signals from ($\phi,\eta$)=(30°, -80°), (-70°, 30°), (-20°,
70°) and (50°, -50°) have all been effectively suppressed.

In the following, the output SINR performance of the two Capon beamformers
(full Q-Capon and Q-Capon) is studied with the DOA and polarization (90°,
1.5°, 90°, 45°) and (90°, 1.5°, 0°, 0°) for SOI and (90°, 30°, 60°, -80°),
(90°,- 70°, 60°, 30°), (90°, -20°, 60°, 70°), (90°, 50°, 60°, -50°) for
interferences. Again, we have set SNR=INR=20dB. All results are obtained by
averaging 1000 Monte-Carlo trials.

Fig. 3 shows the output SINR performance versus SNR with $100$ snapshots,
where the solid-line is for the optimal beamformer with infinite number of
snapshots. For most of the input SNR range, in particular the lower range, the
proposed full Q-Capon beamformer has a better performance than the Q-Capon
beamformer. For very high input SNR values, these two beamformers have a very
similar performance.

Figure 3: Output SINR versus input SNR (snapshots number 100).

Next, we investigate their performance in the presence of DOA and polarization
errors. The output SINR with respect to the number of snapshots is shown in
Fig. 4 in the presence of $1\degree$ error for the SOI, where the real DOA and
polarization parameters are (91°,2.5°,91°,46°) and (91°,2.5°,1°,1°). It can be
seen that the full Q-Capon beamformer has achieved a much higher output SINR
than the Q-Capon beamformer, and this gap increases with the increase of
snapshot number. Fig. 5 shows a similar trend in the presence of a $5\degree$
error. Overall, we can see that the proposed full Q-Capon beamformer is more
robust against array pointing errors.

Figure 4: Output SINR versus snapshot number with SNR=SIR=15dB and 1°error.
Figure 5: Output SINR versus snapshot number with SNR=SIR=15dB and 5°error.

##  V Conclusions

In this paper, a full quaternion model has been developed for adaptive
beamforming based on crossed-dipole arrays, with a new full quaternion Capon
beamformer proposed. Different from previous studies in quaternion-valued
adaptive beamforming, we have considered a quaternion-valued desired signal,
given the recent development in quaternion-valued wireless communications
research. The proposed beamformer has a better performance and a much lower
computational complexity than a previously proposed Q-Capon beamformer and is
also shown to be more robust against array pointing errors, as demonstrated by
computer simulations.

The gradient of a quaternion vector
$\textbf{u}=\emph{{w}}^{\text{H}}\emph{{C}}\boldsymbol{\lambda}^{\text{H}}$
with respect to $\emph{{w}}^{*}$ can be calculated as below:

$\displaystyle\nabla_{\emph{{w}}^{*}}{\textbf{u}}$
$\displaystyle=[\nabla_{\emph{{w}}_{1}^{*}}\textbf{u}\quad\nabla{\emph{{w}}_{2}^{*}}\textbf{u}\quad\text{...}\nabla_{\emph{{w}}_{n}^{*}}\textbf{u}]^{T}$
(23)

where $w_{n}$, $n=1,2,\cdots,N$ is the $n$-th quaternion-valued coefficient of
the beamformer. Then,

$\displaystyle\nabla_{\emph{{w}}_{1}^{*}}{\textbf{u}}$
$\displaystyle=\frac{1}{4}(\nabla_{\emph{{w}}_{1a}}{\textbf{u}}+\nabla_{\emph{{w}}_{1b}}{\textbf{u}}i+\nabla_{\emph{{w}}_{1c}}\textbf{u}j+\nabla_{\emph{{w}}_{1d}}\textbf{u}k)$
(24)

where

$\emph{{w}}_{1}^{*}=\emph{{w}}_{1a}-\emph{{w}}_{1b}i-\emph{{w}}_{1c}j-\emph{{w}}_{1d}k$
(25)

Since $\emph{{w}}_{1a}$ is real-valued, with the chain rule [20], we have

$\displaystyle\nabla_{\emph{{w}}_{1a}}\textbf{u}$
$\displaystyle=\nabla_{\emph{{w}}_{1a}}({\emph{{w}}^{\text{H}}})\emph{{C}}\boldsymbol{\lambda}^{\text{H}}+\emph{{w}}^{\text{H}}\nabla_{\emph{{w}}_{1a}}({\emph{{C}}\boldsymbol{\lambda}^{\text{H}}})$
(26) $\displaystyle=[1\quad 0\quad 0\quad\text{...}\quad
0]\emph{{C}}\boldsymbol{\lambda}^{\text{H}}$

Similarly,

$\displaystyle\nabla_{\emph{{w}}_{1b}}\textbf{u}$ $\displaystyle=[-i\quad
0\quad 0\quad\text{...}\quad 0]\emph{{C}}\boldsymbol{\lambda}^{\text{H}}$
$\displaystyle\nabla_{\emph{{w}}_{1c}}\textbf{u}$ $\displaystyle=[-j\quad
0\quad 0\quad\text{...}\quad 0]\emph{{C}}\boldsymbol{\lambda}^{\text{H}}$
$\displaystyle\nabla_{\emph{{w}}_{1d}}\textbf{u}$ $\displaystyle=[-k\quad
0\quad 0\quad\text{...}\quad 0]\emph{{C}}\boldsymbol{\lambda}^{\text{H}}$

Hence,

$\displaystyle\nabla_{\emph{{w}}_{1}^{*}}\textbf{u}$
$\displaystyle=\frac{1}{4}(4{\text{Real}}(\emph{{C}}\boldsymbol{\lambda}^{\text{H}})_{1})={\text{Real}}(\emph{{C}}\boldsymbol{\lambda}^{\text{H}})_{1}\;,$
(27)

where the subscript $\\{\\}_{1}$ in the last item means taking the first entry
of the vector.

Finally,

$\nabla_{\emph{{w}}^{*}}\textbf{u}={\text{Real}}(\emph{{C}}\boldsymbol{\lambda}^{\text{H}})$
(28)

The gradient of the quaternion vector
$\textbf{v}=\boldsymbol{\lambda}\emph{{C}}^{\text{H}}\emph{{w}}$ with respect
to $\emph{{w}}^{*}$ can be calculated in the same way:

$\displaystyle\nabla_{\emph{{w}}_{1a}}\textbf{v}$
$\displaystyle=\boldsymbol{\lambda}\emph{{C}}^{\text{H}}\nabla_{\emph{{w}}_{1a}}\emph{{w}}+\nabla_{\emph{{w}}_{1a}}(\boldsymbol{\lambda}\emph{{C}}^{\text{H}})\emph{{w}}$
(29) $\displaystyle=\boldsymbol{\lambda}\emph{{C}}^{\text{H}}[1\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$

Similarly,

$\displaystyle\nabla_{\emph{{w}}_{1b}}\textbf{v}$
$\displaystyle=\boldsymbol{\lambda}\emph{{C}}^{\text{H}}[i\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$ (30)
$\displaystyle\nabla_{\emph{{w}}_{1c}}\textbf{v}$
$\displaystyle=\boldsymbol{\lambda}\emph{{C}}^{\text{H}}[j\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$
$\displaystyle\nabla_{\emph{{w}}_{1d}}\textbf{v}$
$\displaystyle=\boldsymbol{\lambda}\emph{{C}}^{\text{H}}[k\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$

Thus, the gradient can be expressed as

$\displaystyle\nabla_{\emph{{w}}_{1}^{*}}\textbf{v}$
$\displaystyle=-\frac{1}{2}(\emph{{C}}\boldsymbol{\lambda}^{\text{H}})_{1}^{*}$
(31)

Finally,

$\nabla_{\emph{{w}}^{*}}\textbf{v}=-\frac{1}{2}(\emph{{C}}\boldsymbol{\lambda}^{\text{H}})^{*}$
(32)

The gradient of $c_{\textbf{w}}={\emph{{w}}^{\text{H}}\emph{{R}}\emph{{w}}}$
can be calculated as follows.

$\nabla_{\emph{{w}}^{*}}c_{\textbf{w}}=[\nabla_{\emph{{w}}_{1}^{*}}c_{\textbf{w}}\quad\nabla_{\emph{{w}}_{2}^{*}}c_{\textbf{w}}\quad\text{...}\quad\nabla_{\emph{{w}}_{n}^{*}}c_{\textbf{w}}]^{\text{T}}$
(33)
$\nabla_{\emph{{w}}_{1}^{*}}c_{\textbf{w}}=\frac{1}{4}(\nabla_{\emph{{w}}_{1a}}c_{\textbf{w}}+\nabla_{\emph{{w}}_{1b}}c_{\textbf{w}}i+\nabla_{\emph{{w}}_{1c}}c_{\textbf{w}}j+\nabla_{\emph{{w}}_{1d}}c_{\textbf{w}}k)$
(34)

Now we calculate the gradient of $c_{\textbf{w}}$ with respect to the four
components of $\emph{{w}}_{1}$.

$\displaystyle\nabla_{\emph{{w}}_{1a}}c_{\textbf{w}}$
$\displaystyle=\nabla_{\emph{{w}}_{1a}}({\emph{{w}}^{\text{H}}\emph{{R}}})\emph{{w}}+\emph{{w}}^{\text{H}}\emph{{R}}\nabla_{\emph{{w}}_{1a}}{\emph{{w}}}$
(35) $\displaystyle=[1\quad 0\quad 0\quad\text{...}\quad
0]\emph{{R}}\emph{{w}}$
$\displaystyle\quad+\emph{{w}}^{\text{H}}\emph{{R}}[1\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$

The other three components are,

$\displaystyle\nabla_{\emph{{w}}_{1b}}c_{\textbf{w}}$ $\displaystyle=[-i\quad
0\quad 0\quad\text{...}\quad 0]\emph{{R}}\emph{{w}}$
$\displaystyle\quad+\emph{{w}}^{\text{H}}\emph{{R}}[i\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$
$\displaystyle\nabla_{\emph{{w}}_{1c}}c_{\textbf{w}}$ $\displaystyle=[-j\quad
0\quad 0\quad\text{...}\quad 0]\emph{{R}}\emph{{w}}$
$\displaystyle\quad+\emph{{w}}^{\text{H}}\emph{{R}}[j\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$
$\displaystyle\nabla_{\emph{{w}}_{1d}}c_{\textbf{w}}$ $\displaystyle=[-k\quad
0\quad 0\quad\text{...}\quad 0]\emph{{R}}\emph{{w}}$
$\displaystyle\quad+\emph{{w}}^{\text{H}}\emph{{R}}[k\quad 0\quad
0\quad\text{...}\quad 0]^{\text{T}}$

Hence,

$\displaystyle\nabla_{\emph{{w}}_{1}^{*}}c_{\textbf{w}}$
$\displaystyle={\text{Real}}(\emph{{R}}\emph{{w}})_{1}-\frac{1}{2}(\emph{{R}}\emph{{w}})_{1}^{*}=\frac{1}{2}(\emph{{R}}\emph{{w}})_{1}$
(36)

Finally,

$\nabla_{\emph{{w}}^{*}}c_{\textbf{w}}=\frac{1}{2}\emph{{R}}\emph{{w}}$ (37)

Combining (28), (32) and (37), with (14), we have

$\nabla_{\emph{{w}}^{*}}l(\emph{{w}},\boldsymbol{\lambda})=\frac{1}{2}(\emph{{R}}\emph{{w}}+\emph{{C}}\boldsymbol{\lambda}^{\text{H}})={\textbf{0}}$
(38)

Further,

$\emph{{w}}=-2\emph{{R}}^{-1}\emph{{C}}\boldsymbol{\lambda}^{\text{H}}$ (39)

Subsituting (39) into (10),

$\displaystyle\boldsymbol{\lambda}=-\frac{1}{2}\emph{{f}}(\emph{{C}}^{\text{H}}\emph{{R}}^{-1}\emph{{C}})^{-1}$
(40)

Finally,

$\emph{{w}}=\emph{{R}}^{-1}\emph{{C}}(\emph{{C}}^{\text{H}}\emph{{R}}^{-1}\emph{{C}})^{-1}\emph{{f}}^{\text{H}}$
(41)

## References

  * [1] R. Compton Jr, “On the performance of a polarization sensitive adaptive array,” _IEEE Transactions on Antennas and Propagation_ , vol. 29, no. 5, pp. 718–725, September 1981.
  * [2] A. Nehorai, K. C. Ho, and B. T. G. Tan, “Minimum-noise-variance beamformer with an electromagnetic vector sensor,” _IEEE Transactions on Signal Processing_ , vol. 47, no. 3, pp. 601–618, March 1999.
  * [3] L. C. Godara, “Application of antenna arrays to mobile communications. ii. beam-forming and direction-of-arrival considerations,” _Proceedings of the IEEE_ , vol. 85, no. 8, pp. 1195–1245, August 1997.
  * [4] Y. G. Xu, T. Liu, and Z. W. Liu, “Output SINR of MV beamformer with one EM vector sensor of and magnetic noise power,” in _Proc. of International Conference on Signal Processing_ , September 2004, pp. 419–422.
  * [5] S. Miron, N. Le Bihan, and J. I. Mars, “High resolution vector-sensor array processing using quaternions,” in _Proc. of IEEE Workshop on Statistical Signal Processing_ , July 2005, pp. 918–923.
  * [6] ——, “Quaternion-music for vector-sensor array processing,” _IEEE Transactions on Signal Processing_ , vol. 54, no. 4, pp. 1218–1229, April 2006\.
  * [7] X. Gong, Y. Xu, and Z. Liu, “Quaternion ESPRIT for direction finding with a polarization sentive array,” in _Proc. of International Conference on Signal Processing_ , October 2008, pp. 378–381.
  * [8] J. W. Tao and W. X. Chang, “A novel combined beamformer based on hypercomplex processes,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 49, no. 2, pp. 1276–1289, 2013.
  * [9] X. R. Zhang, W. Liu, Y. G. Xu, and Z. W. Liu, “Quaternion-valued robust adaptive beamformer for electromagnetic vector-sensor arrays with worst-case constraint,” _Signal Processing_ , vol. 104, pp. 274–283, November 2014\.
  * [10] X. Gou, Y. Xu, Z. Liu, and X. Gong, “Quaternion-capon beamformer using crossed-dipole arrays,” in _Proc. of IEEE International Symposium on Microwave, Antenna, Propagation, and EMC Technologies for Wireless Communications (MAPE)_ , November 2011, pp. 34–37.
  * [11] O. M. Isaeva and V. A. Sarytchev, “Quaternion presentations polarization state,” in _Proc. 2nd IEEE Topical Symposium of Combined Optical-Microwave Earth and Atmosphere Sensing_ , Atlanta, US, April 1995, pp. 195–196.
  * [12] B. J. Wysocki and T. A. Wysocki, “On an orthogonal space-time-polarization block code,” _Journal of Communications_ , vol. 4, no. 1, pp. 20–25, February 2009.
  * [13] W. Liu, “Antenna array signal processing for a quaternion-valued wireless communication system,” in _Proc. the Benjamin Franklin Symposium on Microwave and Antenna Sub-systems (BenMAS)_ , Philadelphia, US, September 2014\.
  * [14] W. R. Hamilton, _Elements of Quaternions_. Longmans, Green, & co., 1866.
  * [15] I. Kantor, A. S. Solodovnikov, and A. Shenitzer, _Hypercomplex Numbers: an Elementary Introduction to Algebras_. New York: Springer Verlag, 1989.
  * [16] X. Zhang, W. Liu, Y. Xu, and Z. Liu, “quaternion-valued robust adaptive beamformer for electromagnetic vector-sensor arrays with worst-case constraint,” _Signal Processing_ , vol. 104, pp. 274–283, November 2014\.
  * [17] M. Hawes and W. Liu, “Design of fixed beamformers based on vector-sensor arrays,” _International Journal of Antennas and Propagation_ , vol. 2015, April 2015.
  * [18] J. Capon, “High-resolution frequency-wavenumber spectrum analysis,” _Proceedings of the IEEE_ , vol. 57, no. 8, pp. 1408–1418, August 1969.
  * [19] O. L. Frost, III, “An algorithm for linearly constrained adaptive array processing,” _Proceedings of the IEEE_ , vol. 60, no. 8, pp. 926–935, August 1972.
  * [20] M. D. Jiang, Y. Li, and W. Liu, “Properties of a general quaternion-valued gradient operator and its application to signal processing,” _Frontiers of Information Technology & Electronic Engineering_, vol. 17, pp. 83–95, February 2016.
  * [21] F. Zhang, “Quaternions and matrices of quaternions,” _Linear algebra and its applications_ , vol. 251, pp. 21–57, January 1997.
  * [22] L. Huang and W. So, “On left eigenvalues of a quaternionic matrix,” _Linear algebra and its applications_ , vol. 323, no. 1, pp. 105–116, January 2001.
  * [23] N. Le Bihan and J. Mars, “Singular value decomposition of quaternion matrices: a new tool for vector-sensor signal processing,” _Signal processing_ , vol. 84, no. 7, pp. 1177–1199, July 2004.