Learning representations that capture rich semantic relationships and accommodate propositional calculus poses a significant challenge. Existing approaches are either contrastive, lacking theoretical guarantees, or fall short in effectively representing the partial orders inherent to rich visual-semantic hierarchies. In this paper, we propose a novel approach for learning visual representations that not only conform to a specified semantic structure but also facilitate probabilistic propositional reasoning. Our approach is based on a new nuclear norm-based loss. We show that its minimum encodes the spectral geometry of the semantics in a subspace lattice, where logical propositions can be represented by projection operators.

§ INTRODUCTION

In the semantic space, concepts convey relations that extend far beyond similarity, such as the case of  hypernymy, inclusion and entailment. Forming the cornerstone of semantic understanding, these transitive relations provide a structured framework for organizing conceptual knowledge, which seamlessly also incorporates the visual domain. In fact, images can be conceptualized as instances of textual elements, occupying the lowest level of the visual-semantic hierarchy [27].

Despite their ubiquity, Euclidean embeddings with the usual inner product do not represent partial orders and thus, visual-semantic data, in the most natural manner. Notably, the commonly used cosine similarity may be  effective to distinguish images of dolphins from images of whales but is oblivious to the fact that both are mammals and semantically distant from tunas. In other words, these common representations fail to elucidate any relations beyond a notion of closeness, rendering the geometry of visual latent spaces incoherent with respect to that of semantic hierarchies [24], which offer a rich set of structural constraints. Failing to harness them leaves more to be learned from the data, hinders interpretability, and renders models inadequate for general-purpose tasks that extend beyond visual similarity assessment and classification, as is the case of representing complex logical queries [11].

Prior approaches that sought to embed transitive relations and the asymmetry inherent to visual-semantic hierarchies, ontologies, Markov decision processes and knowledge graphs, either proposed ad-hoc contrastive loss functions or geometry-inspired approaches. Examples of the latter are measure-based embeddings [26, 28, 18], quasimetrics [21] and hyperbolic geometry [20, 6, 1, 8, 4, 23, 22]. These approaches however, often lack theoretical guarantees.

In this paper, we seek a methodology for learning representations that not only adhere to a semantic structure but also accommodate propositional calculus. Consider a representation space $\mathcal{H}$ and an image encoded therein. Answering any Boolean proposition conditioned on it, amounts to specifying a binary value $y\in\{0,1\}$ and corresponds thus, to a subset of an observation space $\mathcal{Y}=\{0,1\}^c$. Intuitively, we expect the representation space and the observation space to be correlated. In fact, works on semantic linguistics  have conceptualized representations as regions, with the set-theoretical inclusion corresponding to semantic inclusion [9]. In other words, if proposition $p$ entails $q$, the respective observations of $p$ and $q$ in $\mathcal{Y}$ preserve the set-theoretical inclusion and thus, so should the corresponding representations of $p$ and $q$ in $\mathcal{H}$. As we will demonstrate, this rich geometrical structure arises organically from the optimization of a nuclear norm-based loss.

Our paper follows a growing interest in the use of the rank and its surrogates, such as the nuclear norm or the log determinant, to learn representations. Notable examples are the Maximal Code Rate Reduction approach (MCR$^2$) [33], which employs the log determinant, and Maximum Manifold Capacity Representations (MMCR) [34, 17] and Orthogonal Low-rank Embeddings (OLE) [16], which rely on the nuclear norm. Akin to these works, our approach is not contrastive. Unlike them, we demonstrate theoretically how the optimization of the proposed loss yields a subspace Boolean lattice, capturing partial orders, and allowing for a probabilistic formulation of propositional queries. The equivalence between propositional calculus and the calculus of subspaces [19] is what underlies the formulation of quantum logic [3] and has already been repurposed as a geometrical approach to information retrieval [31].

In summary, our contributions are three-fold:

* A new loss function that acts as a surrogate for the information between the joint semantic-visual representation distribution and the marginal representation distribution (Section <ref>).

* We prove that the minimization of the proposed loss guarantees that the visual representations adhere to the spectral geometry of the underlying semantics (Section <ref>).

* We show that the learned representations form a subspace Boolean lattice, where propositions are encoded as projection operators (Section <ref>).

Our learning methodology yields representations suitable for both standard and multi-label classification, as well as for image retrieval from propositional queries. Code is available as supplemental material.

§ LEARNING SEMANTIC SUBSPACES VIA THE NUCLEAR NORM

§.§ A joint visual-semantic low-rank formulation

In this section, we set forth a loss function to learn parsimonious representations that capture a specified semantic structure. We do so by establishing a connection between multi-label classification via low-rank matrix completion [5, 10] and recent works that employ the nuclear norm as a loss [34, 17], or a regularization thereof [16]. Consider an image dataset with $c$ labels and $n$ images. Both the images and the labels shall be represented in some $d$-dimensional vector space. We define the label matrix as $\Yv = [\yv_1\dots\yv_n]\in\{0,1\}^{c\times n}$, and assume that $\Yv$ contains all the structure that we want to impose on the representations $\Xv=[\xv_1\dots\xv_n]\in\mathbb{R}^{d\times n}$. If the latter are amenable to a linear probe, the matrix representing the joint visual-semantic distribution,

\begin{equation}
\Zv:=\begin{bmatrix}\Yv\\\Xv\end{bmatrix}\in\mathbb{R}^{(c+d)\times n},
\end{equation}

is low-rank. Inferring missing labels, or class prototypes, can thus be formulated as finding a complete low-rank matrix that is close to $\Zv$ (for some metric) in all the observed entries [5, 10]. Our initial observation is that we can assume the entire embedding matrix $\Xv$ to be missing, and reframe the problem as that of learning representations. In order to avoid it being ill-posed i.e., representation collapse, we need to ensure that $\Xv$ is non-trivial. This can be achieved by forcing the representations to be full-rank. Using the nuclear norm $\|\cdot\|_\ast$ as a rank-surrogate, the proposed loss function reads as

\begin{equation}
l(\Xv):=\left\|\Zv\right\|_\ast - \alpha \|\Xv\|_\ast + \beta \|\Xv\|_2^2,
\label{eq:the_loss}
\end{equation}

for some $\beta \in (0,1)$ and $\alpha \in (0,1)$, and where $\|\cdot\|_2$ is the operator norm[The operator norm of a matrix is its largest singular value.], which acts as a penalty. The low-rank we seek for $\Zv$ encodes the fact that the column space of $\Xv$ should require no more basis vectors than those required by $\Yv$ i.e., $\Zv$ should be be redundant. Conversely, the high rank we require for $\Xv$ forces it to be informative, unless $\Yv$ is given. This objective is thus tantamount to requiring the joint distribution of $\Xv,\Yv$ to have low entropy and $\Xv$ to have high entropy. Since the entropy of $\Yv$ is fixed, this corresponds to minimizing $H(\Xv,\Yv) - H(\Xv) - H(\Yv)$, which is the negative information between the semantics $\Yv$ and the visual representations $\Xv$. As we state formally in Section <ref>, minimizing this proxy of the negative information yields a spectral embedding of $\Yv$.

Minimizing the loss  $l(\Xv)$ One of our key results rests on the minimization problem of the loss function, formally stated by Theorem <ref>, in Section <ref>. We show that the representations that minimize (<ref>) are given by $\Xv \propto \Vv_Y^T$. In other words, the image representations are proportional to the eigenvectors of the Gram matrix of the semantics $\Yv^\top\Yv$, up to an orthogonal transformation.

The purpose of the squared $\ell_2$-penalty is to ensure that the top singular values of $\Xv$ converge to a common value. Without it, the minimizer is proportional to $\Yv$. The hyperparameter $\alpha < 1$ guarantees that the rank of the minimizers is exactly that of $\Yv$. Table <ref> provides a summary of different nuclear norm-based losses and their minimizers, highlighting the contribution of each term.

Loss $l(\Xv)$     Dim     Argmin

2*$\|\Zv\|_\ast - \alpha \|\Xv\|_\ast$      $d=c$     $\frac{\alpha}{\sqrt{1-\alpha^2}}\Uv \mathbf{\Sigma}_Y \Vv_Y^\top \;:\; \Uv \in O(d)$

$d>c$     $\Uv \begin{bmatrix}\frac{\alpha}{\sqrt{1-\alpha^2}}\mathbf{\Sigma}_Y & \mathbf{0} \\ \mathbf{0} & \mathbf{0}\end{bmatrix} \begin{bmatrix}\Vv_Y^\top \\ \Vv^\top\end{bmatrix} :\; \Uv \in O(d), \Vv \in \mathcal{N}(\Vv_Y)$

2*$\|\Zv\|_\ast - \|\Xv\|_\ast + \beta \|\Xv\|_2$     $d=c$     $\Uv (\omega \Iv_d)\Vv_Y^\top : \; \Uv\in O(d)$

$d>c$     $ \Uv \begin{bmatrix}\omega \Iv_c & \mathbf{0} \\ \mathbf{0} & \mathbf{\Sigma}\end{bmatrix} \begin{bmatrix} \Vv_Y^\top \\ \Vv^\top\end{bmatrix} :\; \Uv\in O(d), \omega \succeq \mathbf{\Sigma}, \Vv \in \mathcal{N}(\Vv_Y)$

2*$\|\Zv\|_\ast - \alpha\|\Xv\|_\ast + \beta \|\Xv\|_2^2$     $d=c$     $\Uv (t \Iv_d)\Vv_Y^\top\; :\; \Uv\in O(d)$

$d>c$     $ \Uv (t \Iv_c) \Vv_Y^\top :\; \Uv\in \mathrm{St}_{c}(\mathbb{R}^d)$

Losses and minimizers for $\Yv = \Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top\in\mathbb{R}^{c\times n}$ rank-$c$ and $\Xv\in\mathbb{R}^{d\times n}$, with $d \geq c$.

Comparison with OLE, MMCR and MCR$^2$ Both OLE [16] and MMCR [34, 17] enforce intra-class low-rank and inter-class high-rank via the nuclear norm and require unit-norm embeddings to avoid collapse. Our method focuses instead on the low-rank assumption of the joint visual-semantic distribution and comes with theoretical guarantees. Additionally, note that the orthogonalization proposed in OLE acts only as a regularizer for cross-entropy training, whereas the loss we propose (<ref>) is standalone. In MCR$^2$ [33], the authors demonstrate that disjoint classes are encoded as orthogonal subspaces and that their sum spans the entire representation space. As shown in Section <ref>, our method also verifies the orthogonality of disjoint classes. However, the corresponding subspaces have the smallest dimension necessary to represent $\Yv$ i.e., the rank of our representations is that of the semantics, regardless of the ambient space. This key difference can be attributed to the use of the nuclear norm which, being the convex envelope of the rank, naturally leads to low-rank solutions.

§.§ Theoretical guarantees and derivations

Our objective for this section is formally derive the minimizer of ($\ref{eq:the_loss}$), with the required auxiliary results. We will denote by $O(d) = \{\Uv \in \mathbb{R}^{d\times d} : \Uv^\top \Uv = \Uv\Uv^\top = \Iv_d\}$ the orthogonal group. The Stiefel manifold of orthonormal $d$-frames in $\mathbb{R}^n$ reads as $\mathrm{St}_d(\mathbb{R}^n)\subset\mathbb{R}^{d\times n}$ and the nullspace of a matrix as $\mathcal{N}$. Recalling that the nuclear norm is the sum of the singular values $\|\Xv\|_\ast = \mathrm{Tr}((\Xv^\top \Xv)^{1/2})$, we first show that it is invariant to orthogonal transformations (proofs are deferred to Appendix <ref>).

Let $\Yv\in\mathbb{R}^{c\times n}$ and $\Xv\in\mathbb{R}^{d\times n}$. For any $\Uv_1 \in O(c), \Uv_2\in O(d)$ and $\Vv\in O(n)$

\begin{equation}
\left\|\begin{bmatrix}\Uv_1 \Yv \\ \Uv_2 \Xv \Vv \end{bmatrix}\right\|_\ast = \left\|\begin{bmatrix}\Yv \Vv^\top \\ \Xv \end{bmatrix}\right\|_\ast
\end{equation}

If we fix the singular values of $\Xv$, the invariance from Lemma <ref> turns the minimization of $\|\cdot\|_\ast$ over $\mathbb{R}^{d\times n}$ into a minimization over $\mathrm{St}_d(\mathbb{R}^n)$. The solution is given by the following Lemma.

Let $\Yv\in\mathbb{R}^{c\times n}$ be a rank-$c$ matrix with SVD $\Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top$, where $\Uv_Y \in O(c)$, $\mathbf{\Sigma}_Y \in\mathbb{R}^{c\times c}$ is diagonal, with singular values $\mu_1 \geq \dots \geq \mu_c$, and $\Vv_Y \in \mathrm{St}_c(\mathbb{R}^n)$. For a rank-$d$ matrix $\Xv \in \mathbb{R}^{d\times n}$ with SVD $\Uv_X\mathbf{\Sigma}_X \Vv_X^\top$ and singular values $\sigma_1 \geq \dots \geq \sigma_d$, let

\begin{equation}
\Vv^\ast = \argmin_{\Vv_X \in \mathrm{St}_d(\mathbb{R}^n)}\left\|\begin{bmatrix}\Yv \\ \Uv_X\mathbf{\Sigma}_X \Vv_X^\top \end{bmatrix}\right\|_\ast.
\end{equation}

* If $c = d$,  $\Vv^\ast = \Vv_Y$ and the min is $\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2}$.

* If $d < c$,  $\Vv^\ast = \begin{bmatrix} \Iv_d & \mathbf{0}\end{bmatrix}\Vv_Y$ and the min is $\sum_{i=1}^{d} \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=d+1}^c \mu_i$.

* If $d > c$,  $\Vv^\ast = \begin{bmatrix} \Vv_Y & \Vv \end{bmatrix}^\top$, with $\Vv^\top \Vv_Y = 0$, and the min is $\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i$.

From Lemma <ref> and Theorem <ref> we can derive our main result, which states that, for the appropriate choice of $\alpha$ and $\beta$, the minimizer of (<ref>) is a spectral embedding of $\Yv^\top \Yv$ with the rank of $\Yv$.

Let $\Yv \in \mathbb{R}^{c\times n}$ be a rank-$c$ matrix with SVD $\Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top$, where $\Uv_Y \in O(c)$, $\mathbf{\Sigma}_Y \in\mathbb{R}^{c\times c}$ is diagonal, with singular values $\mu_1 \geq \dots \geq \mu_c$,  and $\Vv_Y\in \mathrm{St}_c(\mathbb{R}^n)$. For $\beta\in (0,1)$ and $\sqrt{\max\left\{0,1-\frac{4\beta^2\mu_c^2}{c^2}\right\}} \leq \alpha < 1$, define the set

\begin{equation}
\mathcal{X} :=  \argmin_{\Xv \in \mathbb{R}^{d\times n}} \left\{\left\|\begin{bmatrix} \Yv \\ \Xv \end{bmatrix}\right\|_\ast - \alpha\|\Xv\|_\ast + \beta\|\Xv\|_2^2\right\},
\end{equation}

for $d\geq c$. Then,

\begin{equation}
\mathcal{X} =\left\{ \Uv (t \Iv_c) \Vv_Y^\top : \; \Uv\in \mathrm{St}_c(\mathbb{R}^d)\right\},
\end{equation}

where $t > 0$ is the solution to $\sum_{i=1}^c\frac{t}{\sqrt{\mu_i^2 + t^2}} = \alpha c - 2\beta t$.

As formalized in the following lemma, the purpose of the $\ell_2$-penalty via the squared operator norm is to guarantee that the non-trivial singular values of the minimizers of (<ref>) are equal. Without this penalty, the minimizer set for $d=c$ consists of the orbit $\{\Rv\Yv\alpha/\sqrt{1-\alpha^2} \;:\; \Rv\in O(d)\}$.

Let $\Yv \in \mathbb{R}^{c\times n}$ be a rank-$c$ matrix with SVD given by $\Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top$, where $\Uv_Y \in O(c)$, $\mathbf{\Sigma}_Y \in\mathbb{R}^{c\times c}$ is diagonal, with singular values $\mu_1 \geq \dots \geq \mu_c$, and $\Vv_Y\in \mathrm{St}_c(\mathbb{R}^n)$. For $0 < \alpha < 1$, define the set

\begin{equation}
\mathcal{X} := \argmin_{\Xv \in \mathbb{R}^{d\times n}} \left\{\left\|\begin{bmatrix} \Yv \\ \Xv \end{bmatrix}\right\|_\ast - \alpha\|\Xv\|_\ast \right\}.
\end{equation}

\begin{equation}
\mathcal{X} = \left\{\Uv \begin{bmatrix}\frac{\alpha}{\sqrt{1-\alpha^2}}\mathbf{\Sigma}_Y & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{bmatrix} \begin{bmatrix}\Vv_Y^\top \\ \Vv^\top\end{bmatrix} :\; \Uv \in O(d), \Vv \in \mathcal{N}(\Vv_Y)\right\}
\end{equation}

Let $\Yv \in \mathbb{R}^{c\times n}$ be a rank-$c$ matrix with SVD $\Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top$, where $\Uv_Y \in O(c)$, $\mathbf{\Sigma}_Y \in\mathbb{R}^{c\times c}$ is diagonal, with singular values $\mu_1 \geq \dots \geq \mu_c$, and $\Vv_Y\in \mathrm{St}_c(\mathbb{R}^n)$. For $0 < \beta < 1$, define the set

\begin{equation}
\mathcal{X} :=  \argmin_{\Xv \in \mathbb{R}^{d\times n}} \left\{\left\|\begin{bmatrix} \Yv \\ \Xv \end{bmatrix}\right\|_\ast - \|\Xv\|_\ast + \beta\|\Xv\|_2\right\},
\end{equation}

for $d\geq c$. Then,

\begin{equation}
\mathcal{X} =\left\{ \Uv \begin{bmatrix}\omega \Iv_c & \mathbf{0} \\ \mathbf{0} & \mathbf{\Sigma}\end{bmatrix} \begin{bmatrix} \Vv_Y^\top \\ \Vv^\top\end{bmatrix} :\; \Uv\in O(d),\; \omega \Iv \succeq \mathbf{\Sigma},\;\Vv \in \mathcal{N}(\Vv_Y)\right\},
\end{equation}

where $\omega > 0$ is the solution to $\sum_{i=1}^c\frac{\omega}{\sqrt{\mu_i^2 + \omega^2}} = c - \beta$.

Let $Y$ contain $n$ samples from $c$ disjoint classes and

\begin{equation}
\Xv \in \argmin_{\Xv \in \mathbb{R}^{d\times n}} \left\{\left\|\begin{bmatrix} \Yv \\ \Xv \end{bmatrix}\right\|_\ast - \alpha \|\Xv\|_\ast+ \beta\|\Xv\|_2^2\right\}.
\end{equation}

Then, $\yv_i \neq \yv_j \implies \langle \xv_i, \xv_j \rangle = 0$.

Comparison with covariance regularization From Lemma <ref>, the orbit $\{\Rv\Xv : \Rv\in O(d)\}$ contains equivalent embedding matrices. Denote the SVD of $\Xv$ by $\Xv=\Uv\mathbf{\Sigma}\Vv^\top$. Since $\Uv\in O(d)$, we can define an equivalent embedding matrix by writing $\Xv$ in a new basis $\Uv$ such that its covariance is diagonal (assuming centered embeddings) i.e., $\Xv':=\Uv^\top \Xv$ and $\Xv'\Xv'^\top = \Uv^\top \Uv \mathbf{\Sigma} \Vv^\top \Vv \mathbf{\Sigma} \Uv^\top \Uv = \mathbf{\Sigma}^2$. Thus, instead of searching for $\Xv$ that minimizes $\|\Zv\|_\ast$ and maximizes $\|\Xv\|_\ast$, we can limit the search space to the set of matrices which admit the canonical basis of $\mathbb{R}^c$ as left singular vectors i.e., with an SVD $\Xv'=\mathbf{\Sigma} \Vv^\top$. For such matrices, the nuclear norm is given by the trace of $(\Xv\Xv^\top)^{\frac{1}{2}}$ and the problem of maximizing $\|\Xv\|_\ast$ becomes

\begin{align}
&\max_{\Xv\in\mathbb{R}^{c\times n}}\; \sum_{i=1}^c \sqrt{(\Xv\Xv^\top)_{ii}}\nonumber \\
&\;\;\;\mathrm{s.t.} \;\; (\Xv\Xv^\top)_{ij} = 0, \;i\neq j.
\end{align}

The terms of the sum are the standard deviations of each coordinate i.e., $\sqrt{(\Xv\Xv^\top)_{ii}}=\sqrt{\mathrm{Cov}[\Xv_{.,i}]}$. This is simply the covariance regularization proposed in VICReg [2].

§ PROJECTIONS REPRESENT PROPOSITIONAL QUERIES

Given a minimizer of (<ref>) we now derive probabilistic answers to propositions conditioned on the representations. The intrinsic geometry of the data gives rise to logic and probability, akin to the Hilbert space formulation of quantum mechanics [30, 31]. This geometry-induced probabilistic formulation encodes the semantic partial orders, allowing us to perform propositional calculus on the representations, as illustrated in Fig. <ref>.

Subspace Boolean lattice generated by our learning approach. Each basis vector encodes a minterm of 2 literals: $\pv\land\qv$, $\neg\pv\land\qv$ and $\pv\land\neg\qv$. The propositions $\pv$ and $\qv$ are represented by two orthogonal 2-dimensional subspaces. The squared norm of the projection of the representation $\xv$, with $\|\xv\|=1$, over each subspace yields the posterior probability of the corresponding proposition.

§.§ Boolean subspace lattice

Given a full-row rank $\Yv\in\{0,1\}^{c\times n}$, the minimizer of (<ref>) embeds an inclusion Boolean sublattice of the power set $2^{[c]}$, as a subspace lattice of $\mathbb{R}^{c}$. We start by showing that, if we consider the columns of $\Yv=[\yv_1\dots\yv_n]$, denoted $\yv_i \in \{0,1\}^c$, as minterms of $c$ literals (logical propositions), then for any $\yv_i \neq \yv_j$, the corresponding embeddings are orthogonal i.e., $\langle \xv_i, \xv_j \rangle=0$. This allows us to associate more general propositions $\qv$ to subspaces $\mathcal{S}_q \subseteq \mathbb{R}^c$. Logical implication $\pv \implies \qv$ or equivalently, the semantic partial order $\qv \geq \pv$, corresponds in the representation space to the subspace inclusion $\mathcal{S}_p \subseteq \mathcal{S}_q$. This result is a more general version of the orthogonality of disjoint classes of MCR$^2$ [33].

Let $\Yv\in\{0,1\}^{c\times n}$ be a rank-c matrix with SVD denoted $\Uv_Y\mathbf{\Sigma}_Y \Vv_Y^\top$, where $\Uv_Y\in O(c)$, $\mathbf{\Sigma}_Y \in \mathbb{R}^{c\times c}$ and $\Vv_Y \in\mathrm{St}_c(\mathbb{R}^n)\subset\mathbb{R}^{n\times c}$, with rows $\{\vv_i^\top\}_{i\in [n]}$. Let $\mathcal{I}$ be the largest index set such that for $i,j\in\mathcal{I}$ $\yv_i\neq \yv_j$. If $\mathrm{rank}\;\Yv = |\mathcal{I}|$ then $\{\vv_i\}_{i\in\mathcal{I}}$ is an orthogonal basis for $\mathbb{R}^c$.

Recall from Theorem <ref>, that the minimizer of (<ref>) is precisely $\Vv_Y^\top$, up to a global scale and an orthogonal transformation. Combining this with Lemma <ref>, we have that the normalized embeddings corresponding to the minterms $\{\xv_i/\|\xv_i\|_2\}_{i\in\mathcal{I}}$ form an orthonormal basis for the representation space $\mathbb{R}^c$. We will henceforth write this basis as $\{\ev_i\}_{i\in\mathcal{I}}$. Given a unit $\ell_2$-norm representation $\xv$, we have $\sum_{i\in\mathcal{I}} \langle \xv, \ev_i \rangle^2 = 1$ and we can define the probability of the $i$-th minterm $\yv_i$, given the image, as $P(\yv_i | \xv) := \langle \xv, \ev_i \rangle^2$ (by abuse of notation we will use the same symbols for a proposition and the corresponding Bernoulli random variable)[If $\vv$ represents a Boolean proposition $\pv$ and $\xv$ is an embedding, then $p=\cos^2(\angle(\xv,\vv))$ maximizes the mutual information between the binomial variable assigned to a sequence of observations of $\pv|\xv$ and the Bernoulli variable associated with $\pv$ [32].]. Since $0\leq \langle \xv, \ev_i \rangle^2\leq 1$, the representations induce a categorical distribution over the dictionary $\{\yv_i\}_{i\in\mathcal{I}}$. More general propositions $\qv$ over the $c$ labels can be written as a disjunction of the conjunctions  $\{\yv_i\}_{i\in\mathcal{I}}$ i.e., in the disjunctive normal form (DNF).

Let $\Yv\in\{0,1\}^{c\times n}$ verify the conditions of Lemma <ref>. Given $\xv\in\mathbb{R}^d$, with $\|\xv\|_2 = 1$, define the posterior probability of the Bernoulli variable associated with the minterm $\yv_i$ as $P(\yv_i | \xv) := \langle \xv, \ev_i \rangle^2$. Then, $\forall\qv$ such that $\qv = \bigvee_{i\in\mathcal{J}} \yv_i$, for some $\mathcal{J}\subseteq\mathcal{I}$, there is a unique projection operator $\Pv_q$ such that $P(\qv|\xv) = \langle \xv, \Pv_q \xv \rangle$.

If given $\xv$, proposition $\qv$ holds, $\xv$ lies in the corresponding subspace i.e., $\Pv_q \xv =\xv$ and $P(\qv|\xv)=1$. Conversely, if $\qv$ is false then $\Pv_q \xv = 0$ and $P(\qv|\xv)=0$. The angle between the proposition subspace and the latent representation determines the probability $P(\qv|\xv)=\langle \xv, \Pv_q \xv \rangle$. The same reasoning applies to disjunction, conjunction or negation of propositions. The difference being that the sum in (<ref>) is taken over $i\in\mathcal{I}$ s.t. $\yv_i$ implies the disjunction, conjunction or negation, respectively. It follows from this definition that $\Pv_{p \land q} = \Pv_{p} \Pv_{q}$, $\Pv_{p \lor q} = \Pv_{p}  + \Pv_{q} - \Pv_{p} \Pv_{q}$ and $\Pv_{\neg q} = \Iv - \Pv_{q}$.

The set of subspaces of a vector space i.e., its projective geometry, forms a lattice under subspace inclusion [30]. Given subspaces $\mathcal{S}_p$ and $\mathcal{S}_q$, $\mathcal{S}_p \wedge \mathcal{S}_q$ is the set-theoretic intersection i.e., the greatest lower bound or meet. The least upper bound or join, $\mathcal{S}_p \lor \mathcal{S}_q$ is given by the closure of the sum $\mathcal{S}_p + \mathcal{S}_q$. From the one-to-one correspondence between projections and closed subspaces, the lattice structure has an algebraic characterization as $\mathcal{S}_p \leq \mathcal{S}_q \Leftrightarrow \Pv_p \leq \Pv_q \Leftrightarrow \Pv_p = \Pv_p \Pv_q$. If the projections commute then $\Pv_p \wedge \Pv_q = \Pv_p \Pv_q$ and $\Pv_p \lor \Pv_q = \Pv_p + \Pv_q - \Pv_p \Pv_q$. The largest projection is the identity $\Iv$, and the smallest one is the zero operator $0$. We have that $\Pv_p \lor \Pv_p^\perp = \Iv$, $\Pv_p \wedge \Pv_p^\perp = 0$ and $\Pv_p = \Pv_p^{\perp\perp}$, where $\Pv_p^\perp = \Iv - \Pv_p$ is called the orthocomplement of $\Pv_p$. Every subspace lattice is orthomodular [12], which is a weaker version of the distributive property of Boolean algebras. In our case, the subspace lattice is an actual Boolean algebra since, by definition, all the projection operators share the eigenbasis $\{\ev_i\}_{i\in\mathcal{I}}$ and thus commute.

OLE [16]

MCR$^2$ ($\epsilon^2=0.5$) [33]

Convergence of the singular values of $\Xv$ for a multi-label problem with $n=27$ samples, $c=6$ labels and dimension $d=8$. In our method, the top singular values converges to the theoretical limit represented by the dashed line.

§ EXPERIMENTS

We now put forward a basic empirical evaluation of our representation learning approach. We present experiments on standard and multi-label classification tasks. In both cases, we only train the encoder models, not employing linear probes. At inference time, proposition probabilities are derived from the geometry of the representations (Lemma <ref>). Our results show that the proposed loss can surpass traditional cross-entropy training in standard classification. In multi-label settings, our method captures the true semantic geometry, unlike MCR$^2$ or OLE.

Implementation details We implemented (<ref>) in PyTorch, using the subdifferential of the nuclear norm [25] $\partial_{\Xv} \|\Xv\|_\ast = \Uv_X \Vv_X^\top$ as the descent direction. While the nuclear norm is non-smooth, we observed empirical convergence in the all the experiments. All tests were performed on a Tesla T4 GPU with 16GB of memory. During training, the batched output of the image encoder is taken to be exactly $\Xv$, without any normalization or centering. The 1-dimensional subspace for each minterm in $\Yv$ is computed from the training data, via the SVD of the embedding matrix of images for which the minterm holds i.e., if $\Xv = \Uv\mathbf{\Sigma} \Vv^\top$ is the matrix of all representations verifying $\yv_i$, then $\yv_i$ is represented by the subspace spanned by the column of $\Uv$ corresponding to the largest singular value[This is the only non-null singular value if (<ref>) attains its minimum.].

In order for the label matrix $\Yv$ to have full row-rank equal to the number of minterms, as required by Theorem <ref>, we augment it, if necessary, with additional rows corresponding to non-linear Boolean functions of the labels. Consider e.g., a rank-2 $\Yv$ with labels p and q. Theorem <ref> states that the representation space will be $\mathbb{R}^2$. If we assume the basis vectors encode the minterms $p\land\neg q$ and $\neg p \land q$, then we cannot represent the query $p \land q$ as a disjunction (subspace sum) of these minterms (basis). We can address this by introducing a new row in $\Yv$ corresponding to $p \land q$, thus making $\Yv$ rank-3. The sum of the subspace encoding $p \land q$ with that of $p \land\neg q$ encodes $p$ and similarly, the sum of the subspace representing $p \land q$ with that of $\neg p \land q$ encodes $q$. The intersection of the 2-dimensional subspaces of $p$ and $q$ is the 1-dimensional subspace representation of $p \land q$, as desired.

§.§ Synthetic experiments

In order to evaluate the differences between our approach, OLE and MCR$^2$, particularly in the multi-label setting, we conducted experiments on synthetic problems. Fig. <ref> presents a comparison of the convergence of singular values of $\Xv$ between these methods and ours, for a multi-label synthetic problem with $\Yv\in\{0,1\}^{6\times 27}$ (see Appendix <ref>) and $\Xv\in\mathbb{R}^{8\times 27}$. Optimization was performed via gradient descent. The hyperparameters of (<ref>) were set to $\alpha=0.98$ and $\beta=0.7$. OLE and MCR$^2$ ($\epsilon^2=0.5$) were implemented as described in the respective papers, with $\ell_2$-normalization. As per Theorem <ref>, our loss enforces the convergence of top 6 singular values of $\Xv$ to a non-trivial limit and the remaining 2 to zero. The same behavior is not observed in OLE nor MCR$^2$. In Fig. <ref> we plot the matrix of inner products of embeddings upon convergence for the three methods. Our representations verify $\forall\yv_i\neq \yv_j \implies \langle \xv_i, \xv_j\rangle = 0$, forming 6 orthogonal directions. MCR$^2$ produces four orthogonal subspaces, which fail to discriminate between 2 of the 6 minterms. In Appendix <ref>, we show that in standard classification, all three methods represent disjoint classes as orthogonal subspaces.

OLE [16]

MCR$^2$ ($\epsilon^2=0.5$) [33]

Squared inner products between the $\ell_2$-normalized representations for a synthetic multi-label problem with $n=27$ samples, $c=6$ labels and embedding dimension $d=8$.

§.§ Standard classification

CIFAR-10 We assess the efficacy of our loss function in standard classification tasks using the CIFAR-10 dataset [14], which contains 50,000 training images and 10,000 test images, distributed across 10 classes. We applied common data augmentations, including random cropping with a 4-pixel padding resized to $32\times 32$ and random horizontal flipping. We employed a ResNet-18 [13] encoder with a fully connected output layer with dimension $d=10$. Minimization of (<ref>) was carried out via SGD, with a batch size of 512, momentum set at $0.98$, and an initial learning rate of $10^{-4}$, decayed by a factor of $0.1$ after every 100 epochs. We set $\alpha$ and $\beta$ of (<ref>) to $0.997$ and $0.05$, respectively. The model achieved a test accuracy of $92.9\%$. For comparison, the same model trained with a cross-entropy loss attained $92.4\%$. To provide a further insight into the geometry of the representation space, we plot in Fig. <ref> the squared inner products between the 1-dimensional subspaces of each class, and in Fig.<ref> the squared inner products between the $\ell_2$-normalized embeddings of the test set. The convergence of the singular values and the nuclear norm of the embedding matrix $\Xv$ during training are available in Appendix <ref>. In particular, notice that the nuclear norm of the representations increases steadily throughout the epochs.

CIFAR-10 classes

CIFAR-10 representations

CelebA minterms

Geometry of the CIFAR-10 and CelebA representations, from the minimization of (<ref>). Each minterm subspace is set to the principal direction of all the image representations verifying that minterm.

§.§ Multi-label classification

CelebA We showcase the applicability of our approach to the multi-label setting by using a subset of CelebA [15] corresponding to five of the most consistent labels: $\texttt{Men}$, $\texttt{Bald}$, $\texttt{Eyeglasses}$, $\texttt{Wearing Hat}$, and $\texttt{Wearing Necktie}$. This subset comprises 72,900 training images, 8,952 validation images, and 8,303 test images, including 25 minterms. We used a ResNet-34 [13] backbone, with images cropped and resized to $128\times 128$. Due to the significant minterm imbalance, we used a weighted sampler, with the weights set to the reciprocal of the absolute frequencies. Optimization was performed via SGD, with an initial learning rate of $10^{-4}$, momentum of $0.9$ and the same scheduler as CIFAR-10. The hyperparameters were set to $\alpha=0.998$ and $\beta=0.01$. In Fig. <ref> we plot the projections between the 25 minterms. The convergence of the singular values and the nuclear norm of the embedding matrix $\Xv$ are shown in Fig. <ref> of Appendix <ref>. In Fig. <ref> we show example of images whose representations have the largest projection over the 6 different propositions.

Glasses $\land\neg$ Tie $\land$ Hat $\land$ Male

$\neg$ Glasses $\land\neg$ Tie $\land$ Hat $\land$ Male

Bald $\land$ Glasses $\land$ Tie $\land\neg$ Hat $\land$ Male

$\neg$ Bald $\land$ Glasses $\land\neg$ Tie $\land\neg$ Hat $\land\neg$ Male

$\neg$ Bald $\land\neg$ Glasses $\land\neg$ Tie $\land$ Hat $\land\neg$ Male

Bald $\land$ Glasses $\land\neg$ Tie $\land\neg$ Hat $\land$ Male

Examples of images from CelebA dataset whose learned representations have the largest projection over 6 different proposition subspaces.

§ RELATED WORK

A large number of prior works have addressed the problem of representing partial orders [27], especially in the context of learning embeddings of knowledge-graphs and image-caption hierarchies. A notable subset of these include measure-based representations, such as Gaussian embeddings [29], Gaussian mixtures [7], box embeddings [28, 18, 24] and Beta embeddings [26]. Alternatively, several works have approached the problem geometrically, namely via negatively curved manifolds. Hyperbolic embeddings have seen widespread adoption in the literature, owing to their ability to naturally represent tree-like structures [20, 6, 1, 8, 4, 23, 22].

Our work bridges the gap between the aforementioned research on structured representations and works on representation learning based on information theoretical principles, such as MCR$^2$ [33] and MMCR [34, 17]. The latter, in particular, while finding applications in self-supervised learning, uses a nuclear norm-based loss similar to the regularization proposed in [16], as a means to improve image classification.

§ CONCLUSION

In this work, we introduced a novel approach for learning joint visual-semantic representations that adhere to the semantic geometry. Our method is based on a new nuclear norm-based loss function, which we show to yield the spectral embeddings of the semantics. Our approach, being theoretically grounded, diverges both from contrastive learning approaches and methods that simply emphasize class orthogonality to boost cross-entropy classification accuracy. Instead, we show that our representations form a subspace Boolean lattice, which facilitates the definition of probabilistic propositional queries through projection operators. We believe that our work can thus reveal new possibilities for handling complex retrieval tasks and multi-label classification.

Limitations and future work While we provide theoretical guarantees for the minimum of the proposed loss, some limitations of our approach are worthy of mention. Firstly, the use of the nuclear norm leads to the non-smoothness of the loss function. This can make optimization not as straightforward as that of other losses, namely the cross-entropy or the log-determinant. Nevertheless, it should be noted that all the experiments conducted point to good convergence properties when employing SGD with the sub-differential as the descent direction. Secondly, further research is necessary to fully understand the role of the backbone architecture, optimizer, learning-rate and batch-size. Finally, we consider our main contribution to be theoretical and additional experiments would showcase the full potential of the proposed methodology in multi-label classification and retrieval.

§ ACKNOWLEDGEMENT
This work was supported by  LARSyS funding (DOI: 10.54499/LA/P/0083/2020, 10.54499/UIDP/50009/2020, and 10.54499/UIDB/50009/2020] and CMU|Portugal Program, through Fundação para a Ciência e a Tecnologia. M Marques and J Costeira were also supported by the PT SmartRetail project [PRR - 02/C05-i01.01/2022.PC645440011-00000062], through IAPMEI - Agência para a Competitividade e Inovação.

[1]
Mina Ghadimi Atigh, Martin Keller-Ressel, and Pascal Mettes, Hyperbolic Busemann Learning with Ideal Prototypes, Advances in Neural Information Processing Systems, 6 2021, pp. 103–115.

[2]
Adrien Bardes, Jean Ponce, and Yann LeCun, Vicreg: Variance-invariance-covariance regularization for self-supervised learning, International Conference on Learning Representations (ICLR), 2021.

[3]
Garrett Birkhoff and John Von Neumann, The logic of quantum mechanics, Springer, 1975.

[4]
Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth, Neural embeddings of graphs in hyperbolic space, 5 2017.

[5]
Ricardo Cabral, Fernando de la Torre, João Paulo Costeira, and Alexandre Bernardino, Matrix completion for multi-label image classification, Advances in neural information processing systems, vol. 24, 2011.

[6]
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré, From trees to continuous embeddings and back: hyperbolic hierarchical clustering, Advances in Neural Information Processing Systems, 2020, pp. 15065–15076.

[7]
Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan Reddy, Probabilistic entity representation model for reasoning over knowledge graphs, Advances in Neural Information Processing Systems 34 (2021), 23440–23451.

[8]
Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann, Hyperbolic entailment cones for learning hierarchical embeddings, International Conference on Machine Learning, 2018, pp. 1646–1655.

[9]
Maayan Geffet and Ido Dagan, The distributional inclusion hypotheses and lexical entailment, Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 2005, pp. 107–114.

[10]
Andrew Goldberg, Ben Recht, Junming Xu, Robert Nowak, and Jerry Zhu, Transduction with matrix completion: Three birds with one stone, Advances in neural information processing systems 23 (2010).

[11]
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec, Embedding logical queries on knowledge graphs, Advances in neural information processing systems, vol. 31, 2018.

[12]
Samuel S. Holland, The current interest in orthomodular lattices, pp. 437–496, Springer Netherlands, Dordrecht, 1975.

[13]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun, Deep residual learning for image recognition, Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.

[14]
Alex Krizhevsky, Geoffrey Hinton, et al., Learning multiple layers of features from tiny images, Tech. report, Toronto, ON, Canada, 2009.

[15]
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang, Deep learning face attributes in the wild, Proceedings of International Conference on Computer Vision (ICCV), December 2015.

[16]
José Lezama, Qiang Qiu, Pablo Musé, and Guillermo Sapiro, Ole: Orthogonal low-rank embedding-a plug and play geometric loss for deep learning, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 8109–8118.

[17]
Victor Lecomte, Rylan Schaeffer, Berivan Isik, Mikail Khona, Yann LeCun, Sanmi Koyejo, Andrey Gromov, and Ravid Shwartz-Ziv, An information-theoretic understanding of maximum manifold capacity representations, NeurIPS 2023 Workshop on Symmetry and Geometry in Neural Representations, 2023.

[18]
Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum, Smoothing the geometry of probabilistic box embeddings, International Conference on Learning Representations, 2018.

[19]
Peter Mittelstaedt, On the interpretation of the lattice of subspaces of the hilbert space as a propositional calculus, Zeitschrift für Naturforschung A 27 (1972), no. 8-9, 1358–1362.

[20]
Gabriel Moreira, Manuel Marques, João Paulo Costeira, and Alexander Hauptmann, Hyperbolic vs euclidean embeddings in few-shot learning: Two sides of the same coin, Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2024, pp. 2082–2090.

[21]
Facundo Mémoli, Anastasios Sidiropoulos, and Vijay Sridhar, Quasimetric embeddings and their applications, Algorithmica 80 (2018), 3803–3824.

[22]
Maximilian Nickel and Douwe Kiela, Poincaré embeddings for learning hierarchical representations, Advances in Neural Information Processing Systems, 5 2017.

[23]
, Learning continuous hierarchies in the Lorentz model of hyperbolic geometry, International Conference on Machine Learning, 2018, pp. 3779–3788.

[24]
Dhruvesh Palel, Pavitra Dangati, Jay-Yoon Lee, and Andrew Boratko, Michaela nd McCallum, Modeling label space interactions in multi-label classification using box embeddings, International Conference on Learning Representations, 2022.

[25]
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM review 52 (2010), no. 3, 471–501.

[26]
Hongyu Ren and Jure Leskovec, Beta embeddings for multi-hop logical reasoning in knowledge graphs, Advances in Neural Information Processing Systems 33 (2020), 19716–19726.

[27]
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun, Order-embeddings of images and language, arXiv preprint arXiv:1511.06361, 2015.

[28]
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum, Probabilistic embedding of knowledge graphs with box lattice measures, Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2018, pp. 263–272.

[29]
Luke Vilnis and Andrew McCallum, Word representations via gaussian embedding, ICLR, 2015.

[30]
John Von Neumann, Mathematical foundations of quantum mechanics, Princeton University Press, 2018.

[31]
C. J. van Rijsbergen, The geometry of information retrieval, Cambridge University Press, 2004.

[32]
William K Wootters, Optimal information transfer and real-vector-space quantum theory, Quantum Theory: Informational Foundations and Foils (2015), 21–43.

[33]
Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, and Yi Ma, Learning diverse and discriminative representations via the principle of maximal coding rate reduction, Advances in Neural Information Processing Systems 33 (2020), 9422–9434.

[34]
Thomas Yerxa, Yilun Kuang, Eero Simoncelli, and SueYeon Chung, Learning efficient coding of natural images with maximum manifold capacity representations, Advances in Neural Information Processing Systems, vol. 36, 2023.

§ DEFINITIONS

We consider finite dimensional vector spaces over $\mathbb{R}$ with inner product $\langle \uv,\vv \rangle = \uv^\top \vv$ i.e., the usual dot product. The induced norm is thus $\|x\| = \sqrt{\langle \xv, \xv\rangle}$. A linear operator is called symmetric (self-adjoint) if $\Tv=\Tv^\top$. A symmetric operator $\Tv$ is said to be positive if $\langle \Tv\xv, \xv\rangle>0, \forall \xv\in\mathbb{R}^d.$ A projection operator is an idempotent self-adjoint i.e., $\Tv=\Tv^\top=\Tv^2$.

The operator norm is defined as

\begin{equation}
\|\Tv\| = \max_{\xv} \frac{\|\Tv \xv\|}{\|\xv\|}
\end{equation}

and if $\sigma_1\geq\dots\geq\sigma_d$ are singular values of $\Tv$ then $\|\Tv\| = \sigma_1$.

The nuclear norm of an operator, denoted $\|\cdot\|_\ast$, is the $\ell_1$-norm of its singular values. For $\Tv$ with singular values $\sigma_1\geq\dots\geq\sigma_n$, $\|\Tv\|_\ast = \sum_{i=1}^n \sigma_i$. It follows that $\|\Tv\|_\ast = \mathrm{Tr}\left(\left(\Tv^\top\Tv\right)^\frac{1}{2}\right)$. The nuclear norm is the convex envelope of the rank.

A set where a partial order is defined. Given a set $P$ a (weak) partial order is a binary relation $\leq$  between certain pairs of elements that is reflexive (every element relates to itself) $a \leq a$, antisymmetric $a \leq b, b\leq a \Rightarrow a=b$ and transitive $a \leq b, b\leq c \Rightarrow a \leq c$. Strong partial orders are not reflexive. A function between posets is called order-preserving or isotone if $x\leq y \Rightarrow f(x) \leq f(y)$. If we remove antisymmery, we call it a preorder.  Every poset $(X,\preceq)$ is isomorphic to the poset $(P(x),\subseteq)$, i.e., the poset defined on the power set of $X$, with inclusion as the partial order.

Transitive Relation: A relation $R$ is transitive if $x R y, y R z \implies z R z$. E.g., Hypernymy is transitive: “corgi” is an instance of “dog” and “dog” is an instance of “animal” implies “corgi” is an instance of “animal”. Inclusion, or composition is also transitive.

An element $m$ of a poset $P$ is the meet of $x, y$, denoted $x \wedge y$, if $m\leq x, m\leq y$ and if $w \leq x, w\leq y$ then $w \leq m$. Thus, $m$ is the greatest lower bound (infimum). An element $j$  of $P$ is the join of $x,y$ denoted $x\lor y$ if is is the lowest upper bound (supremum).

A poset is a lattice if every two-element subset has a meet and a join.

A lattice is called modular if for all elements a, b and c the implication

\begin{equation}
a \leq c \implies a \lor (b \wedge c) = (a \lor b) \wedge c
\end{equation}

holds. Hence distributivity may not hold.

A bounded lattice, with least and greatest elements denoted $0$ and $1$, respectively, is called complemented if every element $a$ has a complement $b$ such that $a\wedge b = 0$ and $a \lor b = 1$. Orthocomplementation is the operation that maps $a$ to $a^\perp$ such that $a\wedge a^\perp = 0$, $a \lor a^\perp = 1$ and $a^{\perp^\perp}=1$.

§ PROOFS

§.§ Proof of Lemma <ref>

The nuclear norm on the left is equal to $\mathrm{Tr}\left(\left(\Yv^\top \Uv_1^\top \Uv_1 \Yv + \Vv^\top \Xv^\top \Uv_2^\top \Uv_2 \Xv \Vv\right)^{1/2}\right)$ which yields $\mathrm{Tr}\left(\left(\Yv^\top \Yv + \Vv^\top \Xv^\top \Xv\Vv\right)^{1/2}\right)$. Through further manipulation we arrive at $\mathrm{Tr}\left(\left((\Vv \Yv^\top \Yv \Vv^\top + \Xv^\top \Xv\right)^{1/2}\right)$. The nuclear norm on the right is $\mathrm{Tr}\left(\left(\Vv\Yv^\top \Yv\Vv^\top + \Xv^\top\Xv\right)^{1/2}\right)$ and thus equal to that on the left.

§.§ Proof of Theorem <ref>

We prove the case where $d=c$. The other cases follow from this one. Invoking Lemma <ref>, let us remove the gauge freedom and rewrite the problem as

\begin{align}
\min_{\Vv_X \in \mathrm{St}_c(\mathbb{R}^n)}\;&\left\|\begin{bmatrix}\mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top \end{bmatrix}\right\|_\ast.
\end{align}

The cost function reads as

\begin{equation}
f(\Vv_X) := \mathrm{Tr}\left(\left(\Vv_Y\mathbf{\Sigma}_Y^2 \Vv_Y^\top + \Vv_X\mathbf{\Sigma}_X^2 \Vv_X^\top\right)^\frac{1}{2}\right)
\end{equation}

and since any norm is submultiplicative, $f(\Vv_X) \geq \mathrm{Tr}\left(\left(\mathbf{\Sigma}_Y^2 + \Vv_Y^\top \Vv_X\mathbf{\Sigma}_X^2 \Vv_X^\top \Vv_Y\right)^\frac{1}{2}\right)$. We define a lower bound on $f$ as

\begin{equation}
g(\Hv) := \mathrm{Tr}\left(\left(\mathbf{\Sigma}_Y^2 + \Hv \mathbf{\Sigma}_X^2 \Hv^\top \right)^\frac{1}{2}\right) = \left\|\begin{bmatrix}\mathbf{\Sigma}_Y \\ \mathbf{\Sigma}_X \Hv \end{bmatrix}\right\|_\ast,
\end{equation}

for $\|\Hv \| \leq 1$. In particular, we have

\begin{equation}
\min_{\Vv_X \in \mathrm{St}_c(\mathbb{R}^n)}\;f(\Vv_X) \geq \max_{\|\Hv\|\leq 1}\; g(\Hv).
\end{equation}

From the variational characterization of the nuclear norm [25], the right-hand side can be written as

\begin{align}
&\max\;\langle\mathbf{\Omega}_1, \mathbf{\Sigma}_Y\rangle + \langle\mathbf{\Omega}_2, \mathbf{\Sigma}_X \Hv\rangle \nonumber \\
&\;\;\;\mathrm{s.t.}\; \left\|\begin{bmatrix}\mathbf{\Omega}_1 \\ \mathbf{\Omega}_2 \end{bmatrix}\right\| \leq 1, \; \|\Hv\| \leq 1.
\end{align}

In order to maximize the rightmost trace we must have $\Hv = \Iv_c$, which yields the lower bound

\begin{equation}
\min_{\Vv_X \in \mathrm{St}_c(\mathbb{R}^n)}\; f(\Vv_X) \geq g(\Iv_c) = \left\|\begin{bmatrix}\mathbf{\Sigma}_Y \\ \mathbf{\Sigma}_X \end{bmatrix}\right\|_\ast = \mathrm{Tr}\left(\left(\mathbf{\Sigma}_Y^2 + \mathbf{\Sigma}_X^2 \right)^\frac{1}{2}\right).
\end{equation}

It suffices to show that $f$ attains this lower bound for $\Vv_X = \Vv_Y$. In fact,

\begin{align}
f(\Vv_Y) = \left\|\begin{bmatrix}\mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_Y^\top \end{bmatrix}\right\|_\ast = \mathrm{Tr}\left(\left(\begin{bmatrix}\mathbf{\Sigma}_Y^2 & \mathbf{\Sigma}_Y\mathbf{\Sigma}_X \\ \mathbf{\Sigma}_Y\mathbf{\Sigma}_X & \mathbf{\Sigma}_X^2\end{bmatrix}\right)^\frac{1}{2}\right) = \left\|\begin{bmatrix}\mathbf{\Sigma}_Y \\ \mathbf{\Sigma}_X \end{bmatrix}\right\|_\ast
\end{align}

and thus the lower bound is attained.

§.§ Proof of Theorem <ref>

Writing the SVD of $\Xv$ as $\Uv_X \mathbf{\Sigma}_X \Vv_X^\top$, where $\Uv_X\in O(c)$, $\mathbf{\Sigma}_X$ is diagonal and $\Vv_X\in \mathrm{St}_c(\mathbb{R}^n)$, the terms $\|\Xv\|_\ast$ and $\|\Xv\|_2$ only depend on $\mathbf{\Sigma}_X$. Let us rewrite the loss as

\begin{equation}
\left\|\begin{bmatrix} \Yv \\ \Xv\end{bmatrix}\right\|_\ast - \alpha\|\mathbf{\Sigma}_X\|_\ast + \beta\|\mathbf{\Sigma}_X\|_2^2 = \left\|\begin{bmatrix} \Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top \\ \Uv_X\mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \alpha\mathrm{Tr}(\mathbf{\Sigma}_X) + \beta\|\mathbf{\Sigma}_X\|_2^2.
\end{equation}

Using Lemma <ref>, we have the equivalent problem

\begin{align}
\min_{\mathbf{\Sigma}_X \succeq 0, \Vv_X\in \mathrm{St}_c(\mathbb{R}^n)}\left\{ \left\|\begin{bmatrix} \mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \alpha\mathrm{Tr}(\mathbf{\Sigma}_X) + \beta\|\mathbf{\Sigma}_X\|_2^2\right\}
\end{align}

or similarly,

\begin{align}
\min_{\mathbf{\Sigma}_X \succeq  0}\;\left\{ \min_{\Vv_X\in \mathrm{St}_c(\mathbb{R}^n)} \left\|\begin{bmatrix} \mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \alpha\mathrm{Tr}(\mathbf{\Sigma}_X) + \beta\|\mathbf{\Sigma}_X\|_2^2 \right\}.
\end{align}

Denote the singular values of $\Yv$ by $\mu_1 \geq \dots \geq \mu_c$ and those of $\Xv$ by $\sigma_1 \geq \dots \geq \sigma_d$. According to Theorem <ref>, the inner minimization yields $\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i$ for $\Vv_X = \Vv_Y$. Thus,

\begin{align}
\min_{\sigma_1\geq\dots\geq\sigma_d\geq 0}\;\left\{\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i - \alpha\sum_{i=1}^{d}\sigma_i  + \beta \sigma_1^2 \right\}.
\label{eq:main_theorem_loss_in_sigma}
\end{align}

This problem is convex. Let us drop the constraint and consider the relaxed problem

\begin{align}
&\min_{\sigma,t}\; \beta t^2 + \sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} - \alpha \sigma_i + (1-\alpha)\sum_{i=c+1}^d \sigma_i \nonumber \\
&\;\;\mathrm{s.t.}\;\; t - \sigma_i \geq 0,\quad i\in [c] \nonumber \\
&\quad\quad\; \sigma_i \geq 0,\quad  i\in c+1,\dots,d
\end{align}

For dual variables $\lambda_i \geq 0$, $\nu_i \geq 0$ we have the Lagrangian

\begin{equation}
L(\sigma,t;\lambda) = \beta t^2 + \sum_{i=1}^c\left( \sqrt{\mu_i^2 + \sigma_i^2} - \alpha\sigma_i - \lambda_i(t-\sigma_i)\right) + \sum_{i=c+1}^d (1-\alpha)\sigma_i -\nu_i\sigma_i.
\end{equation}

The KKT conditions sufficient for the optimality of the original problem (<ref>) are

\begin{equation}
\begin{cases}
\sigma_1 \geq \dots \geq \sigma_d\geq 0  &\quad\quad(\text{primal feasibility})\\
\lambda_i\geq 0,\quad i \in [c] \geq 0  &\quad\quad(\text{dual feasibility})\\
\nu_i \geq 0,\quad i\in c+1,\dots,d  &\quad\quad(\text{dual feasibility})\\
t-\sigma_i \geq 0,\quad i \in [d]  &\quad\quad(\text{stationarity})\\
\frac{\sigma_i}{\sqrt{\mu_i^2+\sigma_i^2}}+\lambda_i-\alpha = 0,\quad i\in[c] &\quad\quad(\text{stationarity})\\
t = \frac{1}{2\beta}\sum_{i=1}^d \lambda_i &\quad\quad(\text{stationarity})\\
1-\alpha = \nu_i, \quad i = c+1,\dots,d &\quad\quad(\text{stationarity}).
\end{cases}
\label{eq:primal_kkt_main_theorem}
\end{equation}

It follows immediately that, since $\alpha \leq 1$, at the optimum we have $\sigma_i = 0$ for $i=c+1,\dots d$. The dual for the remaining variables is computed as

\begin{align}
\inf_{\sigma,t} L(\sigma,t;\lambda) &= \inf_{t}\left\{\beta t^2-t\sum_{i=1}^c\lambda_i\right\} + \inf_\sigma\left\{\sum_{i=1}^c\left( \sqrt{\mu_i^2 + \sigma_i^2} - (\lambda_i - \alpha)\sigma_i\right)\right\}\nonumber \\
&= -\frac{1}{4\beta}\left(\sum_{i=1}^c\lambda_i\right)^2 + \mu_i\sqrt{1-(\alpha-\lambda_i)^2},
\end{align}

for $\lambda \in [1-\alpha, 1+\alpha]$. The dual problem is then

\begin{align}
&\max_\lambda\; -\frac{1}{4\beta}\left(\sum_{i=1}^c\lambda_i\right)^2 + \mu_i\sqrt{1-(\alpha-\lambda_i)^2} \nonumber \\
&\;\;\mathrm{s.t.}\;\; 0 \leq \lambda_i \leq 1 + \alpha.
\end{align}

The inequality $\lambda_i \leq 1 + \alpha$ is already taken into account in the dual function domain, yielding simply

\begin{align}
&\max_\lambda\; -\frac{1}{4\beta}\left(\sum_{i=1}^c\lambda_i\right)^2 + \mu_i\sqrt{1-(\alpha-\lambda_i)^2} \nonumber \\
&\;\;\mathrm{s.t.}\;\; \lambda_i \geq 0.
\end{align}

The KKT condition for the dual reads $\exists\; \omega_i \geq 0$ subject to

\begin{equation}
\mu_i\frac{\alpha - \lambda_i}{\sqrt{1-(\alpha-\lambda_i)^2}}-\frac{1}{2\beta}\sum_{k=1}^c\lambda_k = \omega_i.
\end{equation}

Set $\omega_i = 0$ (non-binding). From the primal KKT $t=\frac{1}{2\beta}\sum_{i=1}^c\lambda_i$ (<ref>), we have

\begin{equation}
\begin{cases}
\nu_i = 1 - \alpha, \quad i=c+1,\dots,d \\
\lambda_i = \alpha - \frac{t}{\sqrt{\mu_i^2 + t^2}} \\
t=\frac{1}{2\beta}\sum_{i=1}^c\lambda_i \\
\sigma_i = t, \quad i=1\dots,c \\
\sigma_i = 0, \quad i=c+1,\dots,d \\
\end{cases}
\label{eq:theorem_proof_all_kkt}
\end{equation}

It remains to verify the dual feasibility condition $0 \leq \lambda_i \leq 1 + \alpha$. The inequality $\lambda_i \leq 1 + \alpha$, holds since $\lambda_i = \alpha - \frac{t}{\sqrt{\mu_i^2 + t^2}}$ and $\frac{t}{\sqrt{\mu_i^2 + t^2}} < 1$. From $t=\frac{1}{2\beta}\sum_{i=1}^c\lambda_i$ and $\lambda_i = \alpha - \frac{t}{\sqrt{\mu_i^2 + t^2}}$ we have that $t$ is a solution to

\begin{equation}
\alpha c -2\beta t = \sum_{i=1}^c \frac{t}{\sqrt{\mu_i^2 + t^2}}.
\label{eq:theorem_t_is_solution}
\end{equation}

It follows that $t \leq \frac{\alpha c}{2\beta}$ and

\begin{equation}
\lambda_i = \alpha - \frac{t}{\sqrt{\mu_i^2+t^2}} \geq \alpha - \frac{\alpha c }{2\beta\sqrt{\mu_c^2+(\alpha c / 2\beta)^2}}.
\end{equation}

We have thus, that the conditions (<ref>) are sufficient for optimality, provided

\begin{equation}
\alpha - \frac{\alpha c }{2\beta\sqrt{\mu_c^2+(\alpha c / 2\beta)^2}} \geq 0,
\end{equation}

which yields the sufficient condition

\begin{equation}
\alpha \geq \sqrt{\max\left\{0,1-\frac{4\beta^2\mu_c^2}{c^2}\right\}}.
\end{equation}

Concluding the proof, the solution set is

\begin{equation}
\mathcal{X} = \left\{ \Uv (t \Iv_c) \begin{bmatrix} \Vv_Y^\top \\ \Vv^\top\end{bmatrix} \Bigg|\; \Uv\in \mathrm{St}_c(\mathbb{R}^d),\; \Vv \in \mathcal{N}(\Vv_Y)\right\},
\end{equation}

where $t$ is the solution to (<ref>).

§.§ Proof of Lemma <ref>

Writing the SVD of $\Xv$ as $\Uv_X \mathbf{\Sigma}_X \Vv_X^\top$, where $\Uv_X\in O(c)$, $\mathbf{\Sigma}_X$ is diagonal and $\Vv_X\in \mathrm{St}_c(\mathbb{R}^n)$, the terms $\|\Xv\|_\ast$ and $\|\Xv\|_2$ only depend on $\mathbf{\Sigma}_X$. Let us rewrite the loss as

\begin{equation}
\left\|\begin{bmatrix} \Yv \\ \Xv\end{bmatrix}\right\|_\ast - \|\mathbf{\Sigma}_X\|_\ast + \beta\|\mathbf{\Sigma}_X\|_2 = \left\|\begin{bmatrix} \Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top \\ \Uv_X\mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \mathrm{Tr}(\mathbf{\Sigma}_X) + \beta\|\mathbf{\Sigma}_X\|_2.
\end{equation}

Using Lemma <ref>, we have

\begin{align}
\min_{\mathbf{\Sigma}_X \succeq 0, \Vv_X\in \mathrm{St}_c(\mathbb{R}^n)}\left\{ \left\|\begin{bmatrix} \mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \mathrm{Tr}(\mathbf{\Sigma}_X) + \beta\|\mathbf{\Sigma}_X\|_2\right\}
\end{align}

or equivalently,

\begin{align}
\min_{\mathbf{\Sigma}_X \succeq  0}\;\left\{ \min_{\Vv_X\in \mathrm{St}_c(\mathbb{R}^n)} \left\|\begin{bmatrix} \mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \mathrm{Tr}(\mathbf{\Sigma}_X) + \beta\|\mathbf{\Sigma}_X\|_2 \right\}.
\end{align}

Denoting the singular values of $\Yv$ by $\mu_1 \geq \dots \geq \mu_c$ and those of $\Xv$ by $\sigma_1 \geq \dots \geq \sigma_d$ then, according to Theorem <ref>, the inner minimization yields $\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i$. Thus,

\begin{align}
&\min_{\sigma_1\geq\dots\geq\sigma_d\geq 0}\;\left\{\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i - \sum_{i=1}^{d}\sigma_i  + \beta \sigma_1 \right\}
\nonumber \\
=&\min_{\sigma_1\geq\dots\geq\sigma_d\geq 0}\;\left\{\sum_{i=1}^c\left(\sqrt{\mu_i^2 + \sigma_i^2} - \sigma_i\right)  + \beta \sigma_1 \right\}.
\end{align}

This problem is convex and independent of the values of $\sigma_i$ for $i > c$. Let us relax the constraint $\sigma_1\geq\dots\geq\sigma_d\geq 0$ and consider the problem

\begin{align}
&\min_{\sigma,t}\; \beta t + \sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} - \sigma_i \nonumber \\
&\;\;\mathrm{s.t.}\;\; t - \sigma_i \geq 0,\quad i=1,\dots,c.
\end{align}

For $\lambda_i \geq 0$, we have the Lagrangian

\begin{equation}
L(\sigma,t;\lambda) = \beta t + \sum_{i=1}^c\left( \sqrt{\mu_i^2 + \sigma_i^2} - \sigma_i - \lambda_i(t-\sigma_i)\right),
\end{equation}

with KKT conditions

\begin{equation}
\begin{cases}
t-\sigma_i \geq 0 \\
\frac{\sigma_i}{\sqrt{\mu_i^2+\sigma_i^2}}+\lambda_i-1 = 0 \\
\sum_{i=1}^c \lambda_i = \beta.
\end{cases}
\end{equation}

The dual problem is computed from $\inf_{\sigma,t} L(\sigma,t;\lambda)$, which yields $\sum_{i=1}^c\sqrt{1-(1-\lambda_i)^2}\mu_i$ for $\lambda \in [0,2]$ and $\beta = \sum_{i=1}^c \lambda_i$. Hence the dual reads as

\begin{align}
&\max_{\lambda}\; \sum_{i=1}^c \mu_i\sqrt{1-(1-\lambda_i)^2} \nonumber \\
&\;\;\mathrm{s.t.}\;\;  0 \leq \lambda_i \leq 2 \nonumber \\
&\quad\quad \sum_{i=1}^c \lambda_i =\beta
\end{align}

The inequality constraint is already taken into account in the function domain. Defining $z_i = 1-\lambda_i$, the problem can be written as

\begin{align}
&\max_{z}\; \mu_i\sum_{i=1}^c\sqrt{1-z_i^2} \nonumber \\
&\;\;\mathrm{s.t.}\;\; \sum_{i=1}^c z_i = c - \beta
\end{align}

The KKT condition for the dual reads as $-\mu_i\frac{z_i}{\sqrt{1-z_i^2}} -\omega = 0$, from where we obtain $ \lambda_i = 1\pm\frac{\omega}{\sqrt{\mu_i^2 + \omega^2}}$.
Pick $\lambda_i = 1-\frac{\omega}{\sqrt{\mu_i^2 + \omega^2}}$. Plugging this in the primal KKT conditions yields $\sigma_1 = \dots = \sigma_c = \omega$. Finally, from $\sum_{i=1}^c\lambda_i = \beta$, we have that $\omega$ is the solution to

\begin{equation}
\sum_{i=1}^c\frac{\omega}{\sqrt{\mu_i^2 + \omega^2}} = c - \beta.
\end{equation}

Since $\omega \geq 0$, the solution of the relaxed problem $\sigma_i = \omega$, for $i \in [c]$ is also feasible for the original problem, provided we pick $\sigma_{c+1},\dots,\sigma_{d}$ such that $\omega \geq \sigma_{c+1}\geq \dots\geq\sigma_{d}\geq 0$. Combining everything, the solution set is

\begin{equation}
\mathcal{X} = \left\{ \Uv \begin{bmatrix}\omega \Iv_c & \mathbf{0} \\ \mathbf{0} & \mathbf{\Sigma}\end{bmatrix} \begin{bmatrix} \Vv_Y^\top \\ \Vv^\top\end{bmatrix} \Bigg|\; \Uv\in O(d),\; \omega \Iv \succeq \mathbf{\Sigma},\; \Vv \in \mathcal{N}(\Vv_Y)\right\}.
\end{equation}

§.§ Proof of Lemma <ref>

If we write the SVD of $\Xv$ as $\Uv_X \mathbf{\Sigma}_X \Vv_X^\top$, where $\Uv_X\in O(d)$, $\mathbf{\Sigma}_X$ is diagonal and $\Vv_X\in \mathrm{St}_d(\mathbb{R}^n)$ the term $\|\Xv\|_\ast$ is simply the trace of $\mathbf{\Sigma}_X$. Let us rewrite the loss as

\begin{equation}
\left\|\begin{bmatrix} \Yv \\ \Xv\end{bmatrix}\right\|_\ast - \alpha \|\mathbf{\Sigma}_X\|_\ast = \left\|\begin{bmatrix} \Uv_Y \mathbf{\Sigma}_Y \Vv_Y^\top \\ \Uv_X\mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \alpha\mathrm{Tr}(\mathbf{\Sigma}_X).
\end{equation}

Using Lemma <ref>, we have

\begin{align}
\min_{\mathbf{\Sigma_X} \succeq 0, V_X\in \mathrm{St}_c(\mathbb{R}^n)}\; \left\|\begin{bmatrix} \mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \alpha\mathrm{Tr}(\mathbf{\Sigma}_X)
\end{align}

or equivalently,

\begin{align}
\min_{\sigma \geq 0}\;\left\{ \min_{\Vv_X\in \mathrm{St}_c(\mathbb{R}^n)} \left\|\begin{bmatrix} \mathbf{\Sigma}_Y \Vv_Y^\top \\ \mathbf{\Sigma}_X \Vv_X^\top\end{bmatrix}\right\|_\ast - \alpha\mathrm{Tr}(\mathbf{\Sigma}_X)\right\}.
\end{align}

Denote the singular values of $\Yv$ by $\mu_1 \geq \dots \geq \mu_c$ and those of $\Xv$ by $\sigma_1 \geq \dots \geq \sigma_d$. According to Theorem <ref>, the inner minimization yields $\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i$. Thus,

\begin{align}
&\min_{\sigma_1\geq\dots\geq\sigma_d\geq 0}\;\left\{\sum_{i=1}^c \sqrt{\mu_i^2 + \sigma_i^2} + \sum_{i=c+1}^{d}\sigma_i - \alpha \sum_{i=1}^{d}\sigma_i  \right\}.
\end{align}

This problem is convex. Let us relax the constraints $\sigma_1\geq\dots\geq\sigma_d\geq 0$, replacing them by $\sigma_i\geq 0, i\in [d]$. In this relaxation, the derivative w.r.t. $\sigma_k$ yields $\frac{\sigma_k}{\sqrt{\mu_k+\sigma_k^2}}-\alpha$ for $k\in[c]$. The first-order stationarity condition puts thus the optimum at $\sigma_i = \frac{\alpha}{\sqrt{1-\alpha^2}}\mu_i$ for $i\in[c]$. For $k > c$, the derivative w.r.t. $\sigma_k$ yields $1-\alpha > 0$. Given the relaxed constraint $\sigma_i \geq 0, i\in[d]$, the minimum for $i > c$ is therefore attained at $\sigma_i = 0$. Note that the set $\left\{\frac{\alpha}{\sqrt{1-\alpha^2}}\mu_i\right\}_{i\in [c]} \cup \{0\}_{i=c+1}^d$ is feasible for the original problem and thus optimal as well. Combining everything, the solution set is given by

\begin{equation}
\mathcal{X}=\left\{\Uv \begin{bmatrix}\frac{\alpha}{\sqrt{1-\alpha^2}}\mathbf{\Sigma}_Y & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{bmatrix} \begin{bmatrix}\Vv_Y^\top \\ \Vv^\top\end{bmatrix} \;\Bigg|\; \Uv \in O(d),\; \Vv \in \mathcal{N}(\Vv_Y)\right\}.
\end{equation}

§.§ Proof of Lemma <ref>

We start by showing that $\forall i,j \in [n]\; \yv_i = \yv_j \Leftrightarrow \vv_i = \vv_j$. Each column of $\mathbf{\Sigma} \Vv^\top$ can be written as an orthogonal transformation of each column of $\Yv$ by $\Uv^\top\in O(c)$. Therefore, $\yv_i = \yv_j \Leftrightarrow \Uv^\top \yv_i = \Uv^\top \yv_j \Leftrightarrow \mathbf{\Sigma} \vv_i = \mathbf{\Sigma} \vv_j$. Since $\mathbf{\Sigma}$ is square and full-rank, $\mathbf{\Sigma} \vv_i = \mathbf{\Sigma} \vv_j \Leftrightarrow \vv_i = \vv_j$. Together with the definition of $\mathcal{I}$, this implies that $\forall i,j\in\mathcal{I}$ $\vv_i \neq \vv_j$. For the second part, since $\Vv \in \mathrm{St}_c(\mathbb{R}^n)$ we have $\Vv^\top \Vv = \Iv_c$. Thus, $\forall \xv\in\mathbb{R}^c$, $\Vv^\top \Vv \xv  = \xv$. For $i \in \mathcal{I}$, define the sets $\mathcal{J}_i = \{j \in [n] : \yv_j = \yv_i\}$ and note that $\bigcup_{i \in \mathcal{I}} \mathcal{J}_i = [n]$. We can write $\Vv^\top \Vv \xv$ as

\begin{align}
\sum_{i=1}^n \vv_i \langle \vv_i, \xv\rangle  = \sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}_i} \vv_j \langle \vv_j, \xv\rangle =
\sum_{i\in\mathcal{I}} |\mathcal{J}_i| \vv_i \langle \vv_i, \xv\rangle =
\sum_{i\in\mathcal{I}} \sqrt{|\mathcal{J}_i|} \vv_i \langle \sqrt{|\mathcal{J}_i|}\vv_i, \xv\rangle,
\label{eq:equal_cols_proof}
\end{align}

where we used the fact that, by definition, for any two indices $l,k \in \mathcal{J}_i$ we must have $\vv_l=\vv_k=\vv_i$. We can write (<ref>) in matrix notation by defining the matrix $\bar{\Vv}$ with columns $\{\sqrt{|\mathcal{J}_i|} \vv_i\}_{i\in\mathcal{I}}$.  The identity $\forall \xv\in\mathbb{R}^c\;\Vv^\top \Vv \xv = \xv$ becomes $\bar{\Vv}^\top \bar{\Vv} \xv = \xv$. From the hypothesis that $|\mathcal{I}| = \mathrm{rank}\; \Yv = c$, $\bar{\Vv}$ is square and full-rank. Thus, $\forall \xv\in\mathbb{R}^c\;\bar{\Vv}^\top \bar{\Vv} \xv = \xv$ implies that $\bar{\Vv}^\top \bar{\Vv} = \Iv_c$ and we have $\bar{\Vv}\in O(c)$. Therefore, the columns of $\bar{\Vv}$,  $\{\sqrt{|\mathcal{J}_i|} \vv_i\}_{i\in\mathcal{I}}$, form an orthonormal basis for $\mathbb{R}^c$.

§.§ Proof of Lemma <ref>

Since the minterms $\{\yv_i\}_{i\in\mathcal{I}}$ correspond to disjoint events, the posterior is given by the probability of the disjunction of all $\yv_i$ that imply $\qv$. Thus,

\begin{align}
P(\qv|\xv) &= P\left(\bigvee_{i\in\mathcal{I}\;\mathrm{st}\; \yv_i \implies \qv} \yv_i\bigg| \xv\right) \stackrel{(a)}{=} \sum_{i\in\mathcal{I}\;\mathrm{st}\;  \yv_i \implies \qv} P(\yv_i | \xv) \stackrel{(b)}{=}\sum_{i\in\mathcal{I}\;\mathrm{st}\;  \yv_i \implies \qv} \left\langle \xv^\top \ev_i, \ev_i^\top \xv\right\rangle \nonumber \\ &=\left\langle \xv, \left(\sum_{i\in\mathcal{I}\;\mathrm{st}\;  \yv_i \implies \qv} \ev_i \ev_i^\top \right) x\right\rangle \stackrel{(c)}{=} \langle \xv, \Pv_q \xv\rangle,
\label{eq:posterior_probability}
\end{align}

(a) $\{\yv_i\}_{i\in\mathcal{I}}$ correspond to disjoint events; (b) definition of $P(\yv_i|\xv)$; (c) $\Pv_q$ is a projection operator onto the subspace spanned by $\{\ev_i\}_{i\in\mathcal{I}\;\mathrm{st}\; \yv_i \implies \qv}$.

§.§ Additional theoretical results

If we fix the singular values of $\Xv$, the nuclear norm of $\Zv$ can easily be upper bounded. This stems from the triangle inequality

\begin{equation}
\left\|\begin{bmatrix}
\Yv \\
\Xv
\end{bmatrix}\right\|_\ast \leq \left\| \begin{bmatrix} \Yv \\ \mathbf{0}_{d\times n} \end{bmatrix}\right\|_\ast + \left\|\begin{bmatrix} \mathbf{0}_{c\times n} \\ \Xv \end{bmatrix}\right\|_\ast
\end{equation}

being tight if we pick $\Xv$ such that $\Yv\Xv^\top = \Yv^\top \Xv = 0$ (the nuclear norm is additive if the matrices have orthogonal row and column spaces [25]). Hence if $\mathbf{\Sigma}_Y$ denotes the singular values of $\Yv$

\begin{equation}
\max_{\Vv\in\mathrm{St}_d(\mathbb{R}^d)} \left\|\begin{bmatrix}
\Yv \\
\Uv_X \mathbf{\Sigma}_X \Vv_X^\top
\end{bmatrix}\right\|_\ast = \mathrm{Tr}\left(\mathbf{\Sigma}_Y + \mathbf{\Sigma}_X\right)
\end{equation}

Let $\Xv\in\mathbb{R}^{d\times n}$, with $n>d$, be a matrix with unit $\ell_2$-norm columns. Then $\max_{\Xv} \; \|\Xv\|_\ast = d\sqrt{n/d}$ and $\mathrm{argmax}_{\Xv} \; \|\Xv\|_\ast=\sqrt{n/d} \;\Uv\Vv^\top$, for some $\Uv\in O(d)$ and $\Vv\in\mathrm{St}(d,n)$.

Let the SVD be $\Xv=\Uv\mathbf{\Sigma}\Vv^\top$. Then, $\Xv^\top \Xv= \Vv\Sigma^2 \Vv^\top$ and $\mathrm{tr}\;\Xv^\top \Xv=\sum_{i=1}^d\sigma_i^2$. From the normalization, it follows that $\mathrm{tr}\;\Xv^\top \Xv=\sum_{i=1}^n x_i^\top x_i =n$. The maximization of $\|\Xv\|_\ast$ corresponds thus to the optimization problem

\begin{align}
&\max_{\{\sigma_i\}_{i=1}^d}\;\sum_{i=1}^d\sigma_i \nonumber \\
&\;\;\mathrm{s.t.}\sum_{i=1}^d \sigma_i^2=n.
\end{align}

The gradient of the cost is function is $\mathbf{1}\in\mathbb{R}^d$ and his orthogonal to the feasible set at $\sigma_i=\sqrt{\frac{n}{d}},\; i=1,\dots,d$. Thus, $\max_{\Xv}\;\|\Xv\|_\ast=d\sqrt{n/d}$.

For any $\Xv\in\mathbb{R}^{n\times n}$ with singular values $\sigma_1 \geq \dots \geq \sigma_n > 0$,

\begin{equation}
\mathrm{spectrum}\left(\begin{bmatrix}\mathbf{0}_n & \Xv^\top \\ \Xv & \mathbf{0}_n\end{bmatrix}\right) = \bigcup_{i=1}^n \{-\sigma_i, \sigma_i\}
\end{equation}

Denoting the SVD of $\Xv$ by $\Uv\mathbf{\Sigma}\Vv^\top$, it suffices to check that

\begin{equation}
\begin{bmatrix}\mathbf{0}_n & \Xv^\top \\ \Xv & \mathbf{0}_n\end{bmatrix} = \begin{bmatrix}\Vv/\sqrt{2} & -\Vv/\sqrt{2} \\ \Uv/\sqrt{2} & \Uv/\sqrt{2}\end{bmatrix}\begin{bmatrix}\mathbf{\Sigma} & \mathbf{0}_n \\ \mathbf{0}_n & -\mathbf{\Sigma}\end{bmatrix}\begin{bmatrix}\Vv^\top/\sqrt{2} & \Uv^\top/\sqrt{2} \\ -\Vv^\top/\sqrt{2} & \Uv^\top/\sqrt{2}\end{bmatrix}
\end{equation}

is the spectral decomposition of the symmetric matrix with $\Xv$ and $\Xv^\top$ in the off-diagonals.

Let $\Vv_Y, \Vv_X\in\mathrm{St}_c(\mathbb{R}^n)$, for $n>c$, and denote by $\{\sigma_i\}_{i=1}^{2c}$ the singular values of $\Zv \in \mathbb{R}^{2c \times n}$, defined as

\begin{equation}
\Zv:= \begin{bmatrix}
\Vv_Y^\top \\
\Vv_X^\top
\end{bmatrix}.
\end{equation}

Then, $\{\sigma_i\}_{i=1}^{2c} = \bigcup_{i=1}^{c}\left\{\sqrt{1 + \sigma_i(\Vv_Y^\top \Vv_X)}, \sqrt{1 - \sigma_i(\Vv_Y^\top \Vv_X)}\right\}$.
Letting the full SVD of $\Zv$ be $\Uv\mathbf{\Sigma}\Vv^\top$, we have $\Zv\Zv^\top = \Uv\mathbf{\Sigma}^2 \Uv^\top$. Thus, its singular values are given by the square roots of the eigenvalues of $\Zv\Zv^\top$. From $\Vv_Y^\top\Vv_Y = \Vv_X^\top\Vv_X = \Iv_c$ we have

\begin{align}
\sqrt{\lambda_i\left(\Zv\Zv^\top\right)} &= \sqrt{\lambda_i\left(\begin{bmatrix}
\Iv_c & \Vv_Y^\top \Vv_X \\
\Vv_X^\top \Vv_Y & \Iv_c
\end{bmatrix}\right)} = \sqrt{1 + \lambda_i\left(\begin{bmatrix}
\mathbf{0}_c & \Vv_Y^\top \Vv_X \\
\Vv_X^\top \Vv_Y & \mathbf{0}_c
\end{bmatrix}\right)}.
\end{align}

Using Lemma <ref>, this yields $\bigcup_{i=1}^{c}\left\{\sqrt{1 + \sigma_i(\Vv_Y^\top \Vv_X)}, \sqrt{1 - \sigma_i(\Vv_Y^\top\Vv_X)}\right\}$.

For $\Vv_Y \in\mathrm{St}_c(\mathbb{R}^n)$, with $n>c$,

\begin{align}
\min_{\Vv_X \in \mathrm{St}_c(\mathbb{R}^n)} \left\|\begin{bmatrix} \Vv_Y^\top \\ \Vv_X^\top\end{bmatrix}\right\|_\ast  = \left\|\begin{bmatrix} \Vv_Y^\top \\ \Vv_Y^\top\end{bmatrix}\right\|_\ast = \sqrt{2}c
\end{align}

From Lemma <ref> we can write:

\begin{equation}
\left\|\begin{bmatrix} \Vv_Y^\top \\ \Vv_X^\top\end{bmatrix}\right\|_\ast = \sum_{i=1}^c \sqrt{1 + \sigma_i(\Vv_Y^\top \Vv_X)} + \sqrt{1 - \sigma_i(\Vv_Y^\top \Vv_X)}
\end{equation}

Note that $0 \leq \sigma_i(\Vv_Y^\top \Vv_X) \leq 1$ for $i\in [c]$, and

\begin{equation}
\sqrt{1 + \sigma_i} + \sqrt{1 - \sigma_i} \geq \sqrt{2},\quad \sigma_i \in [0,1].
\end{equation}

Therefore we have the lower bound

\begin{equation}
\left\|\begin{bmatrix} \Vv_Y^\top \\ \Vv_X^\top\end{bmatrix}\right\|_\ast \geq \sum_{i=1}^c \sqrt{2} = \sqrt{2}c.
\end{equation}

This bound is tight for $\Vv_X = \Vv_Y$, since $\sigma_i(\Vv_Y^\top \Vv_Y) = \sigma_i(\Iv_c) = 1, i\in [c]$.

§ EXPERIMENTAL DETAILS

listing engine=minted,
listing only,
minted language=#2,
minted style=default,
minted options=
left skip=0pt,
right skip=0pt,

[blue!10!white] (frame.south west) rectangle ([xshift=20pt]frame.north west);

§.§ PyTorch implementation

Below we present an implementation of the loss function (<ref>) in PyTorch, called , as well as the function for computing the minterm directions entitled .
class Nuclear(nn.Module):
def __init__(self, alpha : float, beta : float):
super(Nuclear, self).__init__()
self.a, self.b = alpha, beta

def forward(self, x : torch.Tensor, y : torch.Tensor):
z = torch.cat((y.permute(1,0),
x.permute(1,0)), dim=0)

x_s = torch.linalg.svdvals(x)
z_s = torch.linalg.svdvals(z)
loss = z_s.sum() - self.a * x_s.sum() + self.b * x_s.max()**2
return loss

def compute_minterms_vec(x : torch.Tensor,
y : torch.Tensor,
minterms : torch.Tensor):
minterms_vec = []
for minterm in minterms:
mask = (y == minterm).all(dim=-1)
u, _, _ = torch.linalg.svd(x[mask, :].T)
return torch.cat(minterms_vec, dim=0)

§.§ CIFAR-10

The PyTorch code for the image augmentations used with CIFAR-10 is provided below.
class CIFAR10Transform():
def __init__(self, split):
mu  = (0.4914, 0.4822, 0.4465)
std = (0.2023, 0.1994, 0.2010)

if split.lower() == "train":
self.t = Compose([RandomCrop(32, padding=4),
self.t = Compose([ToTensor(),
def __call__(self, sample):
return self.t(sample)

CIFAR-10 convergence with SGD@1e-4, $\alpha=0.997, \beta=0.05$.

§.§ CelebA

The PyTorch code for the image augmentations used with CelebA is provided below.
class CELEBATransform():
def __init__(self, split):
if split.lower() == "train":
self.t = Compose([Resize((128, 128)),
RandomApply([ColorJitter(0.3,0.3,0.2,0.1)], p=0.5),
self.t = Compose([Resize((128, 128)),

def __call__(self, sample):
return self.t(sample)

CelebA convergence with SGD@1e-4, $\alpha=0.998$, $\beta=0.01$. The accuracy measures the complete match of all labels.

§.§ Synthetic experiments

Fig. <ref> shows the $\Yv$ matrix used in the synthetic multi-label problem described in Section <ref>.

$\Yv \in \mathbb{R}^{6\times 27}$ with 6 labels and 6 minterms.

In Figs. <ref> and <ref> we plot the results of a second synthetic experiment consisting of $n=12$ samples uniformly split between $c=4$ labels and embedding dimension $d=9$. All three methods produce orthogonal subspaces, ours being 1-dimensional.

OLE [16]

MCR$^2$ ($\epsilon^2=0.5)$

Convergence of the singular values of $\Xv$ for a multi-label problem with $n=12$ samples, $c=4$ labels and embedding dimension $d=9$. The dashed line indicates the theoretical limit for the singular values of the minimizer of (<ref>).

OLE [16]

MCR$^2$ ($\epsilon^2=0.5$)

Squared inner products between the optimized representations for a multi-label problem with $n=12$ samples, $c=4$ labels and embedding dimension $d=9$.