Analysing the Linearity of Linguistic Relations in Language Model Embedding Spaces

# Analysing the Linearity of Linguistic Relations in Language Model Embedding Spaces
Source: [https://arxiv.org/html/2609.21655](https://arxiv.org/html/2609.21655)
Vasudevan NedumpozhimanaAffiliation:ADAPT Research CentreAffiliation:Trinity College Dublin, IrelandEmail:[vnedumpo@tcd\.ie](mailto:)Fathima ThekkekaraAffiliation:Indian Institute of Technology BombayAffiliation:Mumbai, IndiaEmail:[fathima@iitb\.ac\.in](mailto:)John KelleherAffiliation:ADAPT Research CentreAffiliation:Trinity College Dublin, IrelandEmail:[john\.kelleher@tcd\.ie](mailto:)

###### Abstract

We propose a framework to analyse how strongly different linguistic relations are linearly encoded in language model embedding spaces\. We formalise linear encoding via a constrained linear approximation over related and unrelated word pairs and apply this to an extended BATS dataset covering inflectional, derivational, lexicographic, and encyclopedic relations in GloVe, RoBERTa, and ModernBERT\. Our experiments show near\-perfect linear encodings for inflectional and derivational relations, but substantially higher errors for lexicographic and encyclopedic relations, especially for one\-to\-many and many\-to\-many associations\. We also find that RoBERTa and ModernBERT generally encode relations more linearly than GloVe\. These results indicate that our framework can reveal which relational structures are most linearly accessible in embeddings, offering a compact tool for probing and comparing relational geometry across models\.

## 1Introduction

Large language models \(LLMs\) and other deep learning–based natural language processing models function by transforming the input text into high‑dimensional numerical vectors called embeddings, in which meaning is represented in a distributed way\. What such an embedding vector represents depends on its numerical values and its position relative to other embedding vectors in the embedding space\. This distributed, high‑dimensional coding makes language processing models powerful but also opaque, because it is hard to see what information—especially about linguistic relationships—is encoded where, and how it influences model behaviour\.

Probing methods are a widely used way to study what kinds of information are encoded in a deep learning based language processing model’s internal representations by testing what information can be recovered from these representations\([Conneau et al\., 2018](https://arxiv.org/html/2609.21655#bib.bib1);[Nedumpozhimana and Kelleher, 2024](https://arxiv.org/html/2609.21655#bib.bib2)\)\. This work proposes a novel framework to analyse the latent representations of language processing models, and goes beyond the standard probing methods in two key ways\. First, rather than simply testing whether particular information is present in an embedding, our framework can be used to understand how it is encoded in the embedding space, and more specifically, whether it is represented in a linear or non‑linear form\. The theoretical inspiration for our approach is the linear representation hypothesis\([Park et al\., 2024](https://arxiv.org/html/2609.21655#bib.bib3)\), which proposes that, for at least some linguistic properties, models organise their internal space linearly\. Such linearly encoded linguistic properties may be more accessible to the model’s downstream computation as compared to other information in the model’s representations, and so may disproportionately influence the model’s behaviour\. Thus, by identifying which information is encoded linearly, we can begin to explain which information strongly drives model behaviour and how we might safely intervene on this behaviour\. Second, while much existing work has applied probing to individual concepts or token‑level properties, we focus on linguistic relations \(such as syntactic or semantic relations\)\. Adopting a relation\-based rather than concept‑based perspective is both novel and advantageous because a relational view asks how models represent the links between elements in text, which drive many downstream behaviours\. The proposed framework is defined for arbitrary linguistic relations \(word\-to\-word, word\-to\-sentence, and sentence\-to\-sentence\), and can handle varying relational complexity \(one\-to\-one, one\-to\-many, and many\-to\-many\)\.

## 2Linearly Encoded Relations

We formalise the concept of the linearity of a relation by defining that any relationrris linearly encoded in the embedding space if there exist two linear operators that map representations of a pair to the same embedding vector if and only if that pair is related\. In linear algebra, a linear relation is one where related pairs\(e1,e2\)\(e\_\{1\},e\_\{2\}\)in a moduleMMover a ringRRsatisfy a linear equationf1​e1\+f2​e2=0f\_\{1\}e\_\{1\}\+f\_\{2\}e\_\{2\}=0, wheref1f\_\{1\}andf2f\_\{2\}are two elements in the ringRR\([Lang, 2002](https://arxiv.org/html/2609.21655#bib.bib8)\)\. In our case, we consider the embedding space as a Module of alldd\-dimensional vectors \(ℝd\\displaystyle\\mathbb\{R\}^\{d\}\) over the ring of alld×dd\\times dsquare matrices \(ℝd×d\\displaystyle\\mathbb\{R\}^\{d\\times d\}\)\. Note that the space of square matrices over matrix addition and matrix multiplication is a ring, and therefore, the set of alldd\-dimensional vectors overd×dd\\times dmatrices is a module\.

Supposerris the target linguistic relation, andt1t\_\{1\}andt2t\_\{2\}are related linguistic expressions \(i\.e\.,\(t1,t2\)∈r\(t\_\{1\},t\_\{2\}\)\\in r\)\. LetEEbe the embedding mapping that maps any linguistic expression to add\-dimensional embedding vector in the embedding space \(ℝd\\displaystyle\\mathbb\{R\}^\{d\}\) and let𝒆1\\displaystyle\{\\bm\{e\}\}\_\{1\}and𝒆2\\displaystyle\{\\bm\{e\}\}\_\{2\}be the twodd\-dimensional embedding vectors of linguistic expressionst1t\_\{1\}andt2t\_\{2\}represented as column matrices\. Now, if the relationrris linearly encoded in the embedding space, then there exist twod×dd\\times dsquare matrices𝑳r\\displaystyle\{\\bm\{L\}\}\_\{r\}and𝑹r\\displaystyle\{\\bm\{R\}\}\_\{r\}that correspond to the relationrrthat maps both𝒆1\{\\bm\{e\}\}\_\{1\}and𝒆2\{\\bm\{e\}\}\_\{2\}to the same vector\. To align this definition with the standard definition of a linear relation, we can multiply the𝑹r\\displaystyle\{\\bm\{R\}\}\_\{r\}operator matrix by−1\-1, so that it will obey the linear equation𝑳r​𝒆1\+𝑹r​𝒆2=0\\displaystyle\{\\bm\{L\}\}\_\{r\}\{\\bm\{e\}\}\_\{1\}\+\{\\bm\{R\}\}\_\{r\}\{\\bm\{e\}\}\_\{2\}=0\. For more notational simplicity, we can concatenate𝒆1\\displaystyle\{\\bm\{e\}\}\_\{1\}and𝒆2\\displaystyle\{\\bm\{e\}\}\_\{2\}to create a single2​d2d\-dimensional vector𝒆12\\displaystyle\{\\bm\{e\}\}\_\{12\}, and column wise concatenate𝑳r\\displaystyle\{\\bm\{L\}\}\_\{r\}and𝑹r\\displaystyle\{\\bm\{R\}\}\_\{r\}to create a singled×2​dd\\times 2dmatrix𝑴r\\displaystyle\{\\bm\{M\}\}\_\{r\}\. Then we can formally define that if a relationrris linearly encoded in the embedding space defined by the embedding mappingEE, then there exists an𝑴r\{\\bm\{M\}\}\_\{r\}, such that:

𝑴r​𝒆12=0⇔\(t1,t2\)∈r\{\\bm\{M\}\}\_\{r\}\{\\bm\{e\}\}\_\{12\}=0\\iff\(t\_\{1\},t\_\{2\}\)\\in r\(1\)

## 3Linear Approximation

Since many linguistic relations will not satisfy the exact linear encoding condition in[1](https://arxiv.org/html/2609.21655#S2.E1), we next define a linear approximation that quantifies how closely a relation can be represented linearly\. Some relations can be approximately encoded linearly; when the embeddings contain noise, this can often be corrected with slight modifications, whereas some relations can only be linearly encoded by excluding extreme instances\. Even for relations that are not exactly linearly encodable, it can still be informative to quantify the degree of linearity they exhibit\.

One can observe that if unrelated pairs of expressions are not considered, a trivial solution \(i\.e\.,𝑴r=0\{\\bm\{M\}\}\_\{r\}=0\) exists for any relation\. To avoid this, it is necessary to include unrelated pairs in addition to related ones\. For related pairs, according to the condition[1](https://arxiv.org/html/2609.21655#S2.E1),𝑴r​𝒆12\{\\bm\{M\}\}\_\{r\}\{\\bm\{e\}\}\_\{12\}should be the zero vector, and hence its Euclidean norm is 0\. In contrast, for unrelated pairs\(t1¯,t2¯\)\(\\bar\{t\_\{1\}\},\\bar\{t\_\{2\}\}\),𝑴r​𝒆¯12\{\\bm\{M\}\}\_\{r\}\\bar\{\{\\bm\{e\}\}\}\_\{12\}should not be the 0 vector \(where𝒆¯12\\bar\{\{\\bm\{e\}\}\}\_\{12\}denotes the concatenated embedding oft1¯\\bar\{t\_\{1\}\}andt2¯\\bar\{t\_\{2\}\}\), and therefore its Euclidean norm is strictly greater than 0\. In this case, by appropriately scaling𝑴r\{\\bm\{M\}\}\_\{r\}, we can ensure that the Euclidean norm is greater than or equal to 1 without affecting the related pairs\. Therefore, we rewrite the condition[1](https://arxiv.org/html/2609.21655#S2.E1)as:

‖𝑴r​𝒆12‖2=0,∀\(t1,t2\)∈r​and​‖𝑴r​𝒆¯12‖2≥1,∀\(t1¯,t2¯\)∉r\\displaystyle\\\|\{\\bm\{M\}\}\_\{r\}\{\\bm\{e\}\}\_\{12\}\\\|^\{2\}=0,\\forall\(t\_\{1\},t\_\{2\}\)\\in r\\text\{ and \}\\\|\{\\bm\{M\}\}\_\{r\}\\bar\{\{\\bm\{e\}\}\}\_\{12\}\\\|^\{2\}\\geq 1,\\forall\(\\bar\{t\_\{1\}\},\\bar\{t\_\{2\}\}\)\\notin r\(2\)
Based on this condition, we define the linear approximation of a linguistic relationrras the matrix𝑴r~\\tilde\{\{\\bm\{M\}\}\_\{r\}\}such that,

𝑴r~=arg⁡min𝑴​\{∑\(t1,t2\)∈r‖𝑴​𝒆12‖2\}​such that,​‖𝑴​𝒆¯12‖2≥1,∀\(t1¯,t2¯\)∉r\\displaystyle\\tilde\{\{\\bm\{M\}\}\_\{r\}\}=\\arg\\min\_\{\\bm\{M\}\}\\big\\\{\\sum\_\{\(t\_\{1\},t\_\{2\}\)\\in r\}\\\|\{\\bm\{M\}\}\{\\bm\{e\}\}\_\{12\}\\\|^\{2\}\\big\\\}\\text\{ such that, \}\\\|\{\\bm\{M\}\}\\bar\{\{\\bm\{e\}\}\}\_\{12\}\\\|^\{2\}\\geq 1,\\forall\(\\bar\{t\_\{1\}\},\\bar\{t\_\{2\}\}\)\\notin r\(3\)
Practically, it is not possible to consider all related pairs and all unrelated pairs, and therefore, we selectpprelated pairs andnnunrelated pairs\. We can concatenate the embeddings ofpprelated pairs to create a2​d×p2d\\times pmatrix𝑷r\{\\bm\{P\}\}\_\{r\}, andnnunrelated pairs to create a2​d×n2d\\times nmatrix𝑵r\{\\bm\{N\}\}\_\{r\}\. Now, we can restate the above optimisation problem as,

𝑴r~=arg⁡min𝑴​\{t​r​\(\(𝑴​𝑷r\)T​\(𝑴​𝑷r\)\)\}​such that,​‖𝑴​𝒗‖2≥1,∀𝒗∈c​o​l​u​m​n​s​\(𝑵r\)\\displaystyle\\tilde\{\{\\bm\{M\}\}\_\{r\}\}=\\arg\\min\_\{\\bm\{M\}\}\\big\\\{tr\(\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)^\{T\}\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)\)\\big\\\}\\text\{ such that, \}\\\|\{\\bm\{M\}\}\{\\bm\{v\}\}\\\|^\{2\}\\geq 1,\\forall\{\\bm\{v\}\}\\in columns\(\{\\bm\{N\}\}\_\{r\}\)\(4\)
This optimisation can be further simplified and formulated as a linear programming problem:

𝒙~=argminx\{𝒄\.𝒙\}such that,𝑨𝒙≥1,𝒙≥0\\displaystyle\\tilde\{\{\\bm\{x\}\}\}=\\arg\\min\_\{x\}\\\{\{\\bm\{c\}\}\.\{\\bm\{x\}\}\\\}\\text\{ such that, \}\{\\bm\{A\}\}\{\\bm\{x\}\}\\geq 1,\{\\bm\{x\}\}\\geq 0\(5\)Where𝑨=\(𝑵rT​𝑼\)⊙\(𝑵rT​𝑼\)\{\\bm\{A\}\}=\(\{\\bm\{N\}\}\_\{r\}^\{T\}\{\\bm\{U\}\}\)\\odot\(\{\\bm\{N\}\}\_\{r\}^\{T\}\{\\bm\{U\}\}\),𝑼\{\\bm\{U\}\}is the left\-singular matrix of𝑷r\{\\bm\{P\}\}\_\{r\},⊙\\odotis the element\-wise multiplication, and𝒄\{\\bm\{c\}\}is the element\-wise square of singular values of𝑷r\{\\bm\{P\}\}\_\{r\}\. \(See Appendix[A](https://arxiv.org/html/2609.21655#A1)for more details\.\) The optimum𝒙\{\\bm\{x\}\}\(i\.e\.,𝒙~\\tilde\{\{\\bm\{x\}\}\}\) for a relationrrfrom this formulation serves two roles: its objective valuec⋅x~c\\cdot\\tilde\{x\}, normalised by the number of related pairs, defines the*approximation error*for relationrr\(see Section[4](https://arxiv.org/html/2609.21655#S4)\), and its components determine the linear operator𝑴r~=d​i​a​g​\(𝒙~\)​𝑼T\\tilde\{\{\\bm\{M\}\}\_\{r\}\}=diag\(\\sqrt\{\\tilde\{\{\\bm\{x\}\}\}\}\)\{\\bm\{U\}\}^\{T\}where𝒙~\\sqrt\{\\tilde\{\{\\bm\{x\}\}\}\}is the element\-wise square root of𝒙~\\tilde\{\{\\bm\{x\}\}\}\.

## 4Are relations encoded linearly in representational spaces?

We conducted a preliminary empirical analysis to check whether the proposed framework can be used to investigate whether linguistic relations are linearly encoded in the representational space of some well\-known language processing models\.

For this experiment, we extended theBATSdataset\([Gladkova et al\., 2016](https://arxiv.org/html/2609.21655#bib.bib4)\), which contains 40 word\-to\-word relations, including 10 Inflectional relations, 10 Derivational relations, 10 Lexicographic relations, and 10 Encyclopedic relations\. For each of these 40 relations, theBATSdataset lists 50 pairs of words for which that relation holds\. To create a dataset for our experiments for each relation inBATS, we manually created 50 more related pairs, and created an extendedBATSdataset with 100 related pairs for each relation\. Many relations we consider in this experiment are one\-to\-many or many\-to\-many, and in such cases, every word is paired individually with every other related word, and hence, the number of data points varies for different relations\. Details of the number of related pairs are shown in Table[1](https://arxiv.org/html/2609.21655#S4.T1)\.

For each of these relations, we also created a set of unrelated pairs by using the words already present in the dataset\. In this process of creating unrelated pairs, we treated the domain \(set of all words that come first in the related pairs\) and the range \(set of all words that come second in the related pairs\) as two different categories\. By this segragation we avoid assuming that the domain and range of a relation should be the same\. We then created the full Cartesian product of domain and range, and treated any pair not in the related set as an unrelated pair\. As in the case of related pairs, the number of unrelated pairs also varies from one relation to another relation, and these details are shown in Table[1](https://arxiv.org/html/2609.21655#S4.T1)\.

To generate representations of words, we used three models: a non\-neural representation model, GloVe\([Pennington et al\., 2014](https://arxiv.org/html/2609.21655#bib.bib7)\); a neural representation model, RoBERTa\([Liu et al\., 2019](https://arxiv.org/html/2609.21655#bib.bib6)\); and one of the most recent neural representation models, ModernBERT\([Warner et al\., 2025](https://arxiv.org/html/2609.21655#bib.bib5)\)\. While generating the GloVe representation, if the word is not in the vocabulary, we randomly assign a fixed 300\-dimensional representation for such words\. To generate RoBERTa and ModernBERT representations, we selected the average final layer token embeddings \(note that a word can have multiple tokens\) generated by the model from the input word\. Then we analysed whether relations are linearly encoded in these representational spaces by linearly approximating these relations and calculating the error of approximation\. The approximation error for a relation is the objective function \([5](https://arxiv.org/html/2609.21655#S3.E5)\) normalised by the number of related pairs; zero error implies perfect linear encoding\.

Table 1:Statistics of dataset and linear approximation errors \(macro average\) ofBATSrelations\.From our empirical analysis, we found that both Inflectional and Derivational relations are linearly encoded in the representational spaces of all three models \(with 0 approximation error\)\. However, for Lexicographic and Encyclopedic relations, none of the models has a perfect linear encoding\. We also found that, although the average values of errors of linear approximations are comparable for all three models, the RoBERTa and ModernBERT average scores are better than the GloVe average score\. This shows that in more recent and powerful language models, relations are encoded more linearly\. However, when we compare RoBERTa with ModernBERT, RoBERTa is better on Lexicography relations, and ModernBERT is better on Encyclopedic relations\.

Generally, we found that relations that are one\-to\-one are more likely to encode linearly in representational space\. For example, all inflectional and derivational relations \(morphological relations\) are one\-to\-one, and we found near\-perfect linear approximations for these relations\. However, for relations with one\-to\-many or many\-to\-many related pairs, i\.e\., Lexicographic and Encyclopedic semantic relations, we observed that it is harder to find a linear approximation\. For example, for one of the lexical relations, ‘part\-whole’, which is a many\-to\-many relation, we got an above 1 average error of approximation for all three representation models \(GloVe: 1\.3017, RoBERTa: 1\.1070, and ModernBERT: 1\.1690\)\. However, for the lexical relation with relatively fewer many\-to\-many related pairs, ‘antonyms\-binary’, we got lower approximation errors \(GloVe: 0\.3309, RoBERTa: 0\.3246, and ModernBERT: 0\.3257\)\. We observed a similar pattern in Encyclopedic relations\.

When we further analysed the Encyclopedic relations, we found that relations that are non\-deterministic or non\-exclusive \(one\-to\-many\) are hard to approximate linearly compared to relations with strong, nearly one\-to\-one associations between entities\. For example, in the case of ‘country\-language’, languages like Malayalam and Hindi have a strong association with India and are therefore more linearly encoded in the embedding space than English, whose association with India is diffuse and non\-exclusive\. Similarly, for the ‘thing–colour’ relation, many related pairs such as ‘banana’ and ‘green’ are context\-dependent/non\-deterministic because a ‘banana’ can be ‘green’, but it can also be ‘yellow’, and for these pairs, we obtained higher approximation errors\.

## 5Conclusion

In this work, we proposed a framework for analysing the linearity of linguistic relations and applied it to 40 word\-to\-word relations of varying complexity in GloVe, RoBERTa, and ModernBERT\. We found that inflectional and derivational relations admit near\-perfect linear encodings, whereas lexicographic and encyclopedic relations—especially one\-to\-many and many\-to\-many mappings—yield substantially higher approximation errors, with RoBERTa and ModernBERT generally encoding relations more linearly than GloVe\. This shows that our framework can pinpoint which relational structures are most linearly accessible in current language models and provides a practical tool for comparing relational geometry across architectures\.

### Acknowledgments

This work was partly supported by the ADAPT Centre which is funded under the SFI Research Centres Programme \(Grant 13/RC/2106\_P2\) and is co\-funded under the European Regional Development Funds\.

## References

- A\. Conneau, G\. Kruszewski, G\. Lample, L\. Barrault, and M\. BaroniWhat you can cram into a single $&\!\#\* vector: probing sentence embeddings for linguistic properties\.InProceedings of the 56th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),Melbourne, Australia,pp\. 2126–2136\.External Links:[Link](https://www.aclweb.org/anthology/P18-1198),[Document](https://dx.doi.org/10.18653/v1/P18-1198)Cited by:[§1](https://arxiv.org/html/2609.21655#S1.p2.1)\.
- Gladkovaet al\.\(2016\)A\. Gladkova, A\. Drozd, and S\. MatsuokaAnalogy\-based detection of morphological and semantic relations with word embeddings: what works and what doesn’t\.\.InProceedings of the NAACL Student Research Workshop,J\. Andreas, E\. Choi, and A\. Lazaridou \(Eds\.\),San Diego, California,pp\. 8–15\.External Links:[Link](https://aclanthology.org/N16-2002/),[Document](https://dx.doi.org/10.18653/v1/N16-2002)Cited by:[§4](https://arxiv.org/html/2609.21655#S4.p2.1)\.
- Lang \(2002\)S\. LangAlgebra\.3 edition,Springer\.Cited by:[§2](https://arxiv.org/html/2609.21655#S2.p1.1)\.
- Liuet al\.\(2019\)Y\. Liu, M\. Ott, N\. Goyal, J\. Du, M\. Joshi, D\. Chen, O\. Levy, M\. Lewis, L\. Zettlemoyer, and V\. StoyanovRoberta: a robustly optimized bert pretraining approach\.arXiv preprint arXiv:1907\.11692\.Cited by:[§4](https://arxiv.org/html/2609.21655#S4.p4.1)\.
- Nedumpozhimana and Kelleher \(2024\)V\. Nedumpozhimana and J\. D\. KelleherTopic aware probing: from sentence length prediction to idiom identification how reliant are neural language models on topic?\.Natural Language Processing,pp\. 1–29\.External Links:[Document](https://dx.doi.org/10.1017/nlp.2024.43)Cited by:[§1](https://arxiv.org/html/2609.21655#S1.p2.1)\.
- Parket al\.\(2024\)K\. Park, Y\. J\. Choe, and V\. VeitchThe linear representation hypothesis and the geometry of large language models\.External Links:2311\.03658,[Link](https://arxiv.org/abs/2311.03658)Cited by:[§1](https://arxiv.org/html/2609.21655#S1.p2.1)\.
- Penningtonet al\.\(2014\)J\. Pennington, R\. Socher, and C\. ManningGlove: global vectors for word representation\.InProceedings of the 2014 conference on empirical methods in natural language processing \(EMNLP\),pp\. 1532–1543\.Cited by:[§4](https://arxiv.org/html/2609.21655#S4.p4.1)\.
- Warneret al\.\(2025\)B\. Warner, A\. Chaffin, B\. Clavié, O\. Weller, O\. Hallström, S\. Taghadouini, A\. Gallagher, R\. Biswas, F\. Ladhak, T\. Aarsen, G\. T\. Adams, J\. Howard, and I\. PoliSmarter, better, faster, longer: a modern bidirectional encoder for fast, memory efficient, and long context finetuning and inference\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 2526–2547\.External Links:[Link](https://aclanthology.org/2025.acl-long.127/),[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.127),ISBN 979\-8\-89176\-251\-0Cited by:[§4](https://arxiv.org/html/2609.21655#S4.p4.1)\.

## Appendix ALP Formulation for Linear Approximation

The optimisation stated in[4](https://arxiv.org/html/2609.21655#S3.E4)for linear approximation has a quadratic objective function with2​d22d^\{2\}variables andnnquadratic constraints\. To simplify this optimisation, we apply singular value decomposition on𝑷r\{\\bm\{P\}\}\_\{r\}\(2​d×p2d\\times pmatrix created by concatenating embeddings ofpprelated pairs\), such that𝑷r=𝑼​Σ​𝑽T\{\\bm\{P\}\}\_\{r\}=\{\\bm\{U\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\. We assume the SVD of𝑴\{\\bm\{M\}\}is𝑸​𝑺​𝑹T\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{R\}\}^\{T\}, then we constrain our search space of𝑴\{\\bm\{M\}\}such that the right singular matrix of𝑴\{\\bm\{M\}\}is the same as the left singular matrix of𝑷r\{\\bm\{P\}\}\_\{r\}\(i\.e\.,𝑹=𝑼\{\\bm\{R\}\}=\{\\bm\{U\}\}\)\. Then we can rewrite the objective function of the above optimisation problem as,

t​r​\(\(𝑴​𝑷r\)T​\(𝑴​𝑷r\)\)=t​r​\(\(𝑸​𝑺​𝑼T​𝑼​Σ​𝑽T\)T​\(𝑸​𝑺​𝑼T​𝑼​Σ​𝑽T\)\)tr\(\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)^\{T\}\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)\)=tr\(\(\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\{\\bm\{U\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)^\{T\}\(\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\{\\bm\{U\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)\)\(6\)By using the unitary property of singular matrices, this can be simplified further\.

t​r​\(\(𝑴​𝑷r\)T​\(𝑴​𝑷r\)\)\\displaystyle tr\(\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)^\{T\}\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)\)=\\displaystyle=t​r​\(\(𝑸​𝑺​Σ​𝑽T\)T​\(𝑸​𝑺​Σ​𝑽T\)\)\\displaystyle tr\(\(\{\\bm\{Q\}\}\{\\bm\{S\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)^\{T\}\(\{\\bm\{Q\}\}\{\\bm\{S\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)\)\(7\)=\\displaystyle=t​r​\(𝑽​ΣT​𝑺T​𝑸T​𝑸​𝑺​Σ​𝑽T\)\\displaystyle tr\(\{\\bm\{V\}\}\\Sigma^\{T\}\{\\bm\{S\}\}^\{T\}\{\\bm\{Q\}\}^\{T\}\{\\bm\{Q\}\}\{\\bm\{S\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)\(8\)=\\displaystyle=t​r​\(𝑽​ΣT​𝑺T​𝑺​Σ​𝑽T\)\\displaystyle tr\(\{\\bm\{V\}\}\\Sigma^\{T\}\{\\bm\{S\}\}^\{T\}\{\\bm\{S\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)\(9\)Here, theΣ\\Sigmawill be a2​d×p2d\\times pmatrix and𝑺\{\\bm\{S\}\}will be ad×2​dd\\times 2dmatrix, and therefore the number of non\-zero diagonal entries ofΣ\\Sigmawill be at most2​d2d, and that of𝑺\{\\bm\{S\}\}will be at mostdd\. Let the diagonal entries ofΣ\\Sigmabeσ1,σ2,…​σ2​d\\sigma\_\{1\},\\sigma\_\{2\},\\dots\\sigma\_\{2d\}and the diagonal entries of𝑺\{\\bm\{S\}\}bes1,s2​…​sds\_\{1\},s\_\{2\}\\dots s\_\{d\}, thenΣT​𝑺T​𝑺​Σ\\Sigma^\{T\}\{\\bm\{S\}\}^\{T\}\{\\bm\{S\}\}\\Sigmawill be a diagonal matrix with entriesσ12​s12,σ22​s22,…​σd2​sd2\\sigma\_\{1\}^\{2\}s\_\{1\}^\{2\},\\sigma\_\{2\}^\{2\}s\_\{2\}^\{2\},\\dots\\sigma\_\{d\}^\{2\}s\_\{d\}^\{2\}\. The trace of a matrix is the sum of its singular values; therefore, thet​r​\(𝑽​ΣT​𝑺T​𝑺​Σ​𝑽T\)tr\(\{\\bm\{V\}\}\\Sigma^\{T\}\{\\bm\{S\}\}^\{T\}\{\\bm\{S\}\}\\Sigma\{\\bm\{V\}\}^\{T\}\)will beσ12​s12\+σ22​s22\+⋯\+σd2​sd2\\sigma\_\{1\}^\{2\}s\_\{1\}^\{2\}\+\\sigma\_\{2\}^\{2\}s\_\{2\}^\{2\}\+\\dots\+\\sigma\_\{d\}^\{2\}s\_\{d\}^\{2\}\. Let𝒙=\(s12,s22,…​sd2\)\{\\bm\{x\}\}=\(s\_\{1\}^\{2\},s\_\{2\}^\{2\},\\ldots s\_\{d\}^\{2\}\)and𝒄=\(σ12,σ22,…​σd2\)\{\\bm\{c\}\}=\(\\sigma\_\{1\}^\{2\},\\sigma\_\{2\}^\{2\},\\ldots\\sigma\_\{d\}^\{2\}\)represented as column matrices\. Then we can rewrite[9](https://arxiv.org/html/2609.21655#A1.E9)in terms of𝒙\{\\bm\{x\}\}and𝒄\{\\bm\{c\}\}as,

t​r​\(\(𝑴​𝑷r\)T​\(𝑴​𝑷r\)\)=𝒄T​𝒙tr\(\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)^\{T\}\(\{\\bm\{M\}\}\{\\bm\{P\}\}\_\{r\}\)\)=\{\\bm\{c\}\}^\{T\}\{\\bm\{x\}\}\(10\)Similarly, the constraints of the optimisation problem can be rewritten as,

‖𝑴​𝒗‖2≥1\\displaystyle\\\|\{\\bm\{M\}\}\{\\bm\{v\}\}\\\|^\{2\}\\geq 1⇔\\displaystyle\\iff\(𝑸​𝑺​𝑼T​𝒗\)T​\(𝑸​𝑺​𝑼T​𝒗\)≥1\\displaystyle\(\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\{\\bm\{v\}\}\)^\{T\}\(\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\{\\bm\{v\}\}\)\\geq 1\(11\)⇔\\displaystyle\\iff𝒗T​𝑼​𝑺T​𝑸T​𝑸​𝑺​𝑼T​𝒗≥1\\displaystyle\{\\bm\{v\}\}^\{T\}\{\\bm\{U\}\}\{\\bm\{S\}\}^\{T\}\{\\bm\{Q\}\}^\{T\}\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\{\\bm\{v\}\}\\geq 1\(12\)⇔\\displaystyle\\iff𝒗T​𝑼​𝑺T​𝑺​𝑼T​𝒗≥1\\displaystyle\{\\bm\{v\}\}^\{T\}\{\\bm\{U\}\}\{\\bm\{S\}\}^\{T\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\{\\bm\{v\}\}\\geq 1\(13\)⇔\\displaystyle\\iff\(\(𝒗T​𝑼\)⊙\(𝒗T​𝑼\)\)​𝒙≥1\\displaystyle\(\(\{\\bm\{v\}\}^\{T\}\{\\bm\{U\}\}\)\\odot\(\{\\bm\{v\}\}^\{T\}\{\\bm\{U\}\}\)\)\{\\bm\{x\}\}\\geq 1\(14\)Where⊙\\odotis the element\-wise multiplication\. Now we can rewrite the optimisation in terms of𝒙\{\\bm\{x\}\},

𝒙~=arg⁡min𝒙​\{𝒄T​𝒙\}​such that,\\displaystyle\\tilde\{\{\\bm\{x\}\}\}=\\arg\\min\_\{\\bm\{x\}\}\\\{\{\\bm\{c\}\}^\{T\}\{\\bm\{x\}\}\\\}\\text\{ such that,\}\(15\)𝑨​𝒙≥𝟏,𝒙≥0\\displaystyle\{\\bm\{A\}\}\{\\bm\{x\}\}\\geq\{\\bm\{1\}\},\{\\bm\{x\}\}\\geq 0\(16\)Where𝑨=\(𝑵rT​𝑼\)⊙\(𝑵rT​𝑼\)\{\\bm\{A\}\}=\(\{\\bm\{N\}\}\_\{r\}^\{T\}\{\\bm\{U\}\}\)\\odot\(\{\\bm\{N\}\}\_\{r\}^\{T\}\{\\bm\{U\}\}\)and𝟏\{\\bm\{1\}\}is a unit column matrix\.

Finally, from the solution of the linear programming problem \(i\.e\.𝒙~\\tilde\{\{\\bm\{x\}\}\}\), we can reconstruct the approximate linear operator matrix𝑴r~\\tilde\{\{\\bm\{M\}\}\_\{r\}\}\. From our formulation, the singular value decomposition of𝑴r~\\tilde\{\{\\bm\{M\}\}\_\{r\}\}is𝑸​𝑺​𝑼T\{\\bm\{Q\}\}\{\\bm\{S\}\}\{\\bm\{U\}\}^\{T\}\. Here, the left singular matrix𝑸\{\\bm\{Q\}\}will cancel out in the optimisation, and therefore we can set it as the identity matrix without affecting the approximation error\. We already assumed that the right singular matrix𝑹\{\\bm\{R\}\}is the same as𝑼\{\\bm\{U\}\}\. The optimum singular value matrix,𝑺\{\\bm\{S\}\}, can be estimated asd​i​a​g​\(𝒙~\)diag\(\\sqrt\{\\tilde\{\{\\bm\{x\}\}\}\}\), where𝒙~\\sqrt\{\\tilde\{\{\\bm\{x\}\}\}\}is the element\-wise square root of𝒙~\\tilde\{\{\\bm\{x\}\}\}\. Then, by combining these, we can write:

𝑴r~=d​i​a​g​\(𝒙~\)​𝑼T\\tilde\{\{\\bm\{M\}\}\_\{r\}\}=diag\(\\sqrt\{\\tilde\{\{\\bm\{x\}\}\}\}\)\{\\bm\{U\}\}^\{T\}Furthermore, the approximation error—i\.e\., the minimum value in[4](https://arxiv.org/html/2609.21655#S3.E4)—is equal to𝒄T​𝒙~\{\\bm\{c\}\}^\{T\}\\tilde\{\\bm\{x\}\}\.