Atomic Recovery Property for Multi-view Subspace-Preserving Recovery

1 Introduction

In many machine learning problems, data in a class lie in a low-dimensional subspace of the high-dimensional ambient space [Li et al., 2019; Wright et al., 2009; Elhamifar and Vidal, 2013; Vidal, 2011]. The examples include but not limited to trajectories of a rigidly moving object in a video and facial images of a subject captured under varying illumination. Accordingly, a data set from multiple classes lie in a union of low-dimensional subspaces, where each subspace corresponds to one class. To exploit the low-dimensional structure of high-dimensional data, in recent years a number of supervised and unsupervised learning methods have been developed for subspace classification [Wright et al., 2009] and subspace clustering [Vidal, 2011], respectively.

1.1 Single-view Subspace-Preserving Recovery

As the theoretical underpinnings for subspace clustering and classification, subspace-preserving recovery has attracted intensive attention in recent years [You and Vidal, 2015; Kaba et al., 2021; Zhang et al., 2021]. Let A ∈ Rd×N be a matrix with the columns drawn from multiple low-dimensional subspaces and y ∈ Rd be a data point from one of these subspaces. Subspace-preserving recovery is to find a representation of y such that y = Ax and the nonzero entries of x correspond to the columns of A lying in the same subspace as y. Such a s representation x is dubbed subspace-preserving [You and Vidal, 2015].

Many pioneering works [Elhamifar and Vidal, 2009; Elhamifar and Vidal, 2010; Soltanolkotabi and Cand´es, 2012] study the subspace-preserving recovery problem in the context of subspace clustering. In [Elhamifar and Vidal, 2009; Elhamifar and Vidal, 2010], the authors showed that Basis Pursuit (BP) algorithm is guaranteed to yield Subspacepreserving representation (SPR) when the data subspaces are independent and disjoint, respectively. The work [Soltanolkotabi and Cand´es, 2012] extends the theoretical condition to the case when the subspaces of interest intersect. In [You and Vidal, 2015], the authors identified two sufficient geometric conditions for both BP and OMP (Orthogonal Matching Pursuit) to achieve subspace-preserving recovery. Inspired by the nullspace property [Foucart and Rauhut, 2013] in classical sparse recovery, Kaba et al. [Kaba et al., 2021] derived the subspace nullspace property for subspace-preserving recovery. To recover the clean signal from its attacked version and determine the attack type, Thaker et al. [Thaker et al., 2022] posed the problem as a block-sparse recovery (BSR) and derived geometric conditions for the success of BSR for the problem. More related works can be found in [Dyer et al., 2013; You et al., 2016; Wang and Xu, 2016; Tsakiris and Vidal, 2018; Wang et al., 2019].

Although advancing our understanding, these prior works on the subspace-preserving recovery theory are only confined to single-view data and cannot be applied for multiview data, which are widespread in various applications such as multimodal biometrics recognition [Shekhar et al., 2013; Ren et al., 2022] and multi-view clustering [Abavisani and Patel, 2018; Tang and Liu, 2022; Guo et al., 2022; Chen et al., 2023].

1.2 Multi-view Subspace Classification and Clustering

In many real-world applications, data is usually multi-view in nature, such as a video containing both audio signals and visual frames and images of a 3D object captured in distinct viewpoints. To exploit the consistent and complementary information among multiple views, various multi-view subspace clustering and multi-view subspace classification methods have been developed in recent years [Shekhar et al., 2013; Wang et al., 2023]. For instance, Shekhar et al. [Shekhar et al., 2013] developed a Joint Sparse Representation (JSR) based multi-view subspace classification method for multimodal biometrics recognition. Wang et al. [Wang et al., 2023] proposed a multi-view sparse subspace clustering (MSSC) method based on JSR. More related works can be found in the references [Bahrampour et al., 2015; Zhang et al., 2017; Abavisani and Patel, 2018].

Despite their empirical success and superiority over singleview methods, few theoretical results are reported to justify their effectiveness. In this work, we introduce a new notion dubbed Multi-view Subspace-Preserving Recovery, which plays a central role in the success of multi-view subspace clustering and classification methods. However, it is unclear under what conditions these multi-view subspace clustering and classification methods generate Multi-view SubspacePreserving Representation (MSPR). The goal of this work is to fill this gap.

1.3 Paper Contributions

In this paper, we make the following contributions:

1. We derive a necessary and sufficient condition termed as Atomic Recovery Property (ARP for short) for multiview subspace-preserving recovery. To the best of our knowledge, this is the first work to address the multiview subspace-preserving recovery problem.
2. We provide a geometrically more interpretable characterization of ARP by comparing the unit atomic norm ball w.r.t. the atomic set of multi-view data points in a cluster and that w.r.t. the atomic set of remaining multiview data points.
3. Based on the proposed ARP theory, we derive novel theoretical results for multi-view subspace clustering and classification, respectively.

1.4 Paper Organization

The remainder of the paper is arranged as below. Section 2 introduces some background knowledge and formulates the problem of multi-view subspace-preserving recovery. Section 3 presents the main results along with the comparison with other prior works. In Sections 4-5, we apply the proposed theory for multi-view subspace clustering and classification, respectively. Finally, Section 6 concludes.

2 Preliminaries and ProblemFormulation

2.1 Notations

For better readability, scalars, vectors, matrices and sets are represented with italic letters (e.g., x), boldface lowercase letters (e.g., x), boldface capital letters (e.g., X) and calligraphic capital letters (e.g., X), respectively. Denote by [N] the set of integers from 1 to N. For any vector x ∈ RN , supp(x) denotes its support set, i.e., supp(x) = {i : xi ̸= 0}. Analogously, for any matrix X ∈ RN×V , rowsupp(X) denotes its row support set, i.e., the index set of nonzero rows of X. Denote X(i, :) and X(:, j) as the i-th row and j-th column of X, respectively. The ℓ1,2 norm of X is defined as ∥X∥1,2 = ∑Ni=1 ∥X(i, :)∥2. To distinguish multi-view data from single-view data, a dot is added on the above of the variable (e.g., ˙A). Table 1 summarizes the key notations and acronyms used in this paper.

2.2 Single-view Subspace-Preserving Recovery

Let A = [a1, · · · , aN] ∈ Rd×N denote a matrix with nonzero columns collected from a union of K subspaces ⋃Kk=1 Sk, where each subspace corresponds to one class. Given any new nonzero point y ∈ Sk for some k, subspacepreserving recovery aims to find a representation c ∈ RN of y such that (1) y = Ac, and (2) the nonzero entries of c only correspond to the columns of A lying in the same subspace as y. Such a representation c is dubbed a subspace-preserving representation (SPR) [You and Vidal, 2015], which are formally defined as follows.

Definition 1. (Subspace-Preserving Representation, SPR) [You and Vidal, 2015] Given y ∈ Sk, a solution c to y = Ac is said to be a subspace-preserving representation (SPR) of y if and only if supp(c) ⊂ Ik.

Due to the promising performance and theoretical guarantee, sparse representation based subspace classification and clustering methods [Wright et al., 2009; Elhamifar and Vidal, 2013] have attracted massive interest in recent years. Their success also motivate a plenty of theoretical works [You and Vidal, 2015; You et al., 2016; Wang and Xu, 2016; Kaba et al., 2021] to study conditions for sparse representation algorithms such as BP and OMP to give SPR solutions.

2.3 Multi-view Subspace-Preserving Recovery

Now we consider the setting of multi-view data. Assume that there are V views and K classes in total. For each view v ∈ [V ], let Av = [av1 , · · · , avN ] ∈ Rdv×N denote a matrix with nonzero columns collected from a union of K subspaces ⋃Kk=1 S v k where dv is the v-th view data dimension. For simplicity, let ˙A = {Av , ∀v ∈ [V ]}. Let Ik and I-k denote the index sets of samples in and out the kth class. Let Avk and Av-k denote the sub-matrices of Av containing and excluding samples from the subspace S v k for k ∈ [K] and v ∈ [V ], respectively. For each class k ∈ [K], let ˙Ak = {Avk , ∀v ∈ [V ]}, ˙A-k = {Av-k , ∀v ∈ [V ]}, and ˙ Sk = {S v k , ∀v ∈ [V ]}. For simplicity, we say ˙y ∈ ˙ Sk if yv ∈ S v k holds for each view v ∈ [V ].

To leverage the correlation among multiple views, [Shekhar et al., 2013] tackles the multi-view subspace classification by solving the joint sparse optimization program

where ∥C∥1,2 = ∑mi=1 ∥C(i, :)∥2 encourages the representation vector in different views to share the same sparsity pattern. To understand the correctness of this approach, we first propose the Multi-view SPR and consider the following theoretical questions.

Definition 2. (Multi-view Subspace-Preserving Representation, MSPR) Given a multi-view sample ˙y ∈ ˙ Sk, a representation matrix C satisfying yv = AvC(:, v), ∀v ∈ [V ] is said to be a Multi-view Subspace-Preserving Representation (MSPR) of ˙y if and only if rowsupp(C) ⊂ Ik.

1. What are the theoretical conditions under which the solution to the model (1) is a MSPR?
2. Is there any geometric interpretable characterization of theoretical conditions for (1) to produce MSPR?
3. How to apply the theoretical results on MSPR for multiview subspace clustering and classification?

3 Main Results

In this section, we aim to provide answers to the questions concerning MSPR in Section 2. Before showing the main results, we first introduce the definition of atomic norm and extend it for multi-view data.

3.1 Multi-viewAtomic Norm

Let A be an origin-symmetric (i.e., a ∈ A if and only if (iff) -a ∈ A) set. The definition of atomic norm is introduced as follows.

Definition 3. [Chandrasekaran et al., 2012] Given the atomic set A, the atomic norm of x with respect to A is defined as

where conv(A) is the convex hull of the set A.

If the atomic set A is centrally symmetric about the origin, the gauge function ∥ · ∥A is a norm [Chandrasekaran et al., 2012]. In this case, we have

Many popular norms such as the ℓ1 norm and matrix nuclear norm are special cases of atomic norm with appropriate choice of the atomic set [Chandrasekaran et al., 2012]. The dual norm of ∥ · ∥A is defined by

where ⟨x, a⟩ = tr(xT a) and tr(·) represents the trace of a matrix. Now we generalize the atomic norm to the multi-view setting.

Definition 4. Given themulti-viewatomic set ˙A = {Av }Vv=1 , the Multi-view Atomic Norm (MAN) of the multi-view data ˙x = {xv }Vv=1 with respect to ˙A is defined as

Remark 1. Note that when V = 1, the multi-view atomic norm reduces to the atomic norm in Definition 3.

3.2 Atomic Recovery Property

Before showing the theoretical results, we first introduce some useful lemmas.

Proof. For any t > 0 such that y ∈ t · conv( ˙A1), we have y ∈ t · conv( ˙A2). So

Recalling the definition of MAN gives ∥y∥ ˙A1 ≥ ∥y∥ ˙A2 .

Recall that Avk is the submatrix of Av including samples from the k-th subspace S v k of the v-th view and Av-k is the submatrix of Av by excluding the samples in S v k . Let Avk and Av-k denote the set of columns of ±Avk and ±Av-k , respectively. We can define the multi-view atomic sets ˙Ak = {Avk }Vv=1 and ˙A-k = {Av-k }Vv=1 . Then we have the following results to characterize the relationship among the three multi-view atomic norms, i.e., ∥ · ∥ ˙A, ∥ · ∥ ˙Ak and ∥ · ∥ ˙A-k .

Lemma 2. For any optimal solution C∗ to the model (1), let ˙yk and ˙y-k are defined such that yvk = AvkC∗ (Ik, :) and yv-k = Av-kC∗ (I-k, :) for v = 1, · · · , V . Then we have

Proof. On the one hand, since ˙Ak, ˙A-k ⊂ ˙A and by Lemma 1, there holds

On the other hand, according to the definition of the Multiview Atomic Norm (MAN) we have

It follows that

Combining (4) and (7) completes the proof.

Now we give the definition of ARP for the multi-view data ˙A, which is beneficial for producing MSPR.

Definition 5. (Atomic Recovery Property, ARP) The multiview data ˙A is said to satisfy the Atomic Recovery Property (ARP) if for all k ∈ [K] and ˙y ∈ ˙ Sk\{ ˙0}, we have

Remark 2. The ARP means that it is more concise in terms of the atomic norm to represent any nonzero sample ˙y in ˙ Sk by using ˙Ak than ˙A-k.

With the definitions above, we have the following result.

Theorem 1. The solution to (1) is a MSPR for all k ∈ [K] and ˙y ∈ ˙ Sk\{˙0} if and only if ˙A satisfies the ARP.

Proof. First, we prove that any solution C∗ = C∗ ( ˙y, ˙A) to (1) is aMSPR for any k ∈ [K] and ˙y ∈ ˙ Sk\{˙0} if ˙A satisfies the ARP. That is, we aim to prove C∗ (I-k, :) = 0. Denote

The second equality above uses the fact that yv = AvC∗ (: , v) = AvkC∗ (Ik, v) + Av-kC∗ (I-k, v). The proof consists of the following two steps

1. Step 1: If rv = 0, ∀v ∈ [V ], C∗ (I-k, :) = 0.
2. Step 2: Prove rv = 0, ∀v ∈ [V ] by contradiction.

Proof of Step 1: For any v ∈ [V ], since yv ∈ S v k and AvkC∗ (Ik, v) ∈ S v k , we have rv ∈ S v k according to Eq. (9). If rv = 0, yv = AvkC∗ (Ik, v) = Aδk(C∗ (:, v)). Let ∆k(C∗ ) be the matrix by arranging δk(C∗ (:, v)) as its v-th column for any v ∈ [V ]. Then ∆k(C∗ ) is also feasible to the JSR model (1). If ∆-k(C∗ ) ̸= 0, we have

This contradicts with the optimality of C∗ to (1). Thus ∆-k(C∗ ) = 0. So if we can prove rv = 0 for any v ∈ [V ], the desired conclusion holds. Now we prove it by contradiction.

Proof of Step 2: If ˙r ̸= ˙0, since ˙A satisfies the ARP and ˙r ∈ ˙ Sk, there holds

For ease of simplicity, let yvk = AvkC∗ (Ik, v), ∀v ∈ [V ]. Accordingly, yv = yvk + rv , ∀v ∈ [V ]. It follows that

This is a contradiction. So ˙r = 0 and C∗ is subspacepreserving.

Conversely, if any solution C∗ to (1) is a MSPR for any k ∈ [K] and ˙y ∈ ˙ Sk\{0}, we will prove ˙A satisfies the ARP

by contradiction. Assume that there exists some ˙y violating the ARP, i.e., ∥ ˙y∥Ak ≥ ∥ ˙y∥A-k . Consider the following two optimization problems

(12)

By the hypothesis we know that C∗ is a MSPR and rowsupp(C∗ ) ⊂ Ik. So C∗ (Ik, :) is also an optimal solution to the problem (11). It follows that

Define a matrix ˜C ∈ RN×V such that ˜C(Ik, :) = 0 and ˜C(I-k, :) = C∗-k . Then we have ∥˜C∥1,2 ≤ ∥C∗-k ∥1,2 = ∥C∗ ∥1,2 and yv = Av ˜C(:, v), ∀v ∈ [V ]. Thus ˜C is feasible to (1) and also an optimal solution to (1). However, according to the definitions of C∗-k in (12) and ˜C, we know that ˜C is not a MSPR. This contradicts with the hypothesis that any solution to (1) is a MSPR. This completes the proof.

Remark 3. Theorem 1 shows that ARP is a necessary and sufficient condition for the model (1) to generate MSPR.

3.3 Geometric Characterization of ARP

The unit ball with respect to the atomic set ˙A is defined as B ˙A := { ˙y : ∥ ˙y∥ ˙A ≤ 1}.

Theorem 2. The multi-view data ˙A satisfies the ARP if and only if for all k ∈ [K], there holds

where rinte (B ˙Ak ) denotes the relative interior of B ˙Ak .

Proof. Firstly, we prove that ˙A satisfies the ARP if Eq. (13) holds for all k ∈ [K]. For all k ∈ [K] and ˙y ∈ ˙ Sk\{ ˙0}, define ˙z such that zv = yv ∥ ˙y∥ ˙A-k for v ∈ [V ]. It follows that ˙z ∈ ˙ S and ∥˙z∥ ˙A-k = 1. Thus, ˙z ∈ ˙ Sk ∩ B ˙A-k ⊆ rinte (B ˙Ak ). Accordingly, ∥˙z∥ ˙Ak < 1. Recall the definition of ˙z, this is equivalent to ∥∥∥∥ ˙y ∥ ˙y∥ ˙A-k ∥∥∥∥ ˙Ak < 1. This gives

Conversely, we prove that if ˙A satisfies the ARP, Eq. (13) holds for all k ∈ [K]. For any ˙y ∈ ˙ Sk ∩ B ˙A-k , ∥ ˙y∥ ˙Ak < ∥ ˙y∥ ˙A-k ≤ 1. Therefore, we have ˙y ∈ B ˙Ak .

For single-view data, we have the following result.

Corollary 1. The single-view data A satisfies the ARP if and only if for all k ∈ [K], there holds

Lemma 3. Let A be the set of columns of A and -A. We have BA = K(A).

Proof. We first prove that BA ⊂ K(A). ∀y ∈ BA, we have ∥y∥A = 1. According to Eq. (2), there exists {ca, a ∈ A} such that y = ∑a∈A caa, ca ≥ 0 and ∑a∈A ca = 1. Thus, y lies in the convex hull of ±A and we have y ∈ K(A).

Then we prove K(A) ⊂ BA. ∀y ∈ K(A), there exists {λa}a∈A (λa ≥ 0) such that y = ∑a∈A λaa and ∑a∈A λa = 1. According to the definition of atomic norm (2), there holds ∥y∥A ≤ 1 and y ∈ BA.

Corollary 2. The single-view data A satisfies the ARP if and only if for all k ∈ [K], there holds

Here K(A) = conv(±A) denotes the symmetrized convex hull of the columns of A and rinte (K(Ak)) is the relative interior of K(Ak). Therefore, Theorem 2 for single-view data in the previous work [Kaba et al., 2021] can be regarded as a special case of our result in Theorem 2 when V = 1.

Next, we derive another geometric characterization for ARP based on the multi-view incoherence and multi-view circumradius, which are defined as follows.

Definition 6. (Multi-view Incoherence) The multi-view incoherence between two multi-view datasets ˙P = {Pv }Vv=1 and ˙Q= {Qv }Vv=1 is defined as

where ˙p = {pv }Vv=1 and ˙q = {qv }Vv=1 .

Remark 4. By substituting ˙A-k and ˙ Sk into Eq. (16), we

where Sdv-1 = {z ∈ Rdv : ∥z∥2 = 1} is the unit sphere in Rdv . The multi-view incoherence µM ( ˙A-k, ˙ Sk ) measures how close the multi-view samples in other clusters from the underlying subspaces corresponding to the k-th cluster.

Definition 7. (Multi-viewCircumradius) The multi-view circumradius of ˙Ak = {Avk }Vv=1 is defined as

where ˙u = {uv }Vv=1 .

The multi-view circumradius RM ( ˙Ak ) characterizes the distribution of the samples of ˙Ak in the corresponding subspaces ˙ Sk .

Theorem 3. The multi-view data ˙A satisfies the ARP if for all k ∈ [K], there holds

Proof. For any k ∈ [K] and ˙y ∈ ˙ Sk\{˙0}, we prove that ∥ ˙y∥ ˙Ak < ∥ ˙y∥ ˙A-k . The proof has the following two steps

We first consider the following two row-sparse optimization problems

Proof of Step 1: Since yv ∈ S v k = span(Ak) for each v ∈ [V ], the problem (20) is feasible and the optimal solution C∗k exists. The dual problem of (20) can be formulated as

For each view v ∈ [V ], decompose uvk into two orthogonal components uvk = uv,∥ k +uv,⊥ k , where uv,∥ ∈ S v k and uv,⊥ k ∈ S v,⊥ k . Here S v,⊥ k denotes the orthogonal complement of S v k in Rdv . Then we have (Avk )T uvk = (Avk )T uv,∥ k for any v ∈ [V ]. It follows that

The second equality above uses the fact that u⊥k is orthogonal to S v k = span(Avk ). Let ˙u∥k = {uv,∥ k }V v=1 . Since uv,∥ k ∈ S v k , ∀v ∈ [V ], there holds ˙u∥k ∈ ˙ Sk. According to the definition of RM ( ˙Ak ) in Eq. (18), we have

By the strong duality of (20) and (22) and noting yv ∈ S v k , there holds

Combining Eq. (24) and Eq. (25) gives ∥ ˙y∥ ˙Ak = ∥C∗k ∥1,2 ≤ (∑Vv=1 ∥yv ∥2) RM ( ˙Ak ) .

Proof of Step 2: If the problem (21) is not feasible, ∥ ˙y∥ ˙A-k = ∥∥C∗-k ∥∥1,2 = +∞ and the desired conclusion holds. Otherwise, since C∗-k is feasible to (21), we can write

Multiplying both sides of the above equation on the left by (yv )T /∥yv ∥2, we have

It follows that

Since yv ̸= 0 and ∥yv ∥2 > 0, the equation (26) above indicates that µM ( ˙A-k, ˙ Sk ) > 0 and

This finishes the proof of Step 2.

Combining Steps 1 and 2 and Eq. (19), we have ∥ ˙y∥ ˙Ak < ∥ ˙y∥ ˙A-k . This completes the proof of the theorem.

3.4 Comparison with PriorWorks

To further clarify the novelty and contributions of the paper, we compare our results with prior related works. Table 2 compares the important prior works and this work on SPR. Note that most prior works are concerned with the single-view data instead of multi-view data considered in this paper.

Comparison to [Soltanolkotabi and Cand´es, 2012]. In [Soltanolkotabi and Cand´es, 2012], the authors shows that the SR model Basis Pursuit (BP) can give SPR for a specific point y in Sk rather than all points in Sk if

where the dual direction v(y,Ak) of y is defined as

Here λ(y,Ak) is called the dual point and defined as an optimal solution with minimum Euclidean norm to the problem

We can apply it to all samples in Sk and get the condition

where V := {v (y,Ak) , ∀y ∈ Sk}. Although the condition above provides clear geometric insights for the success of SSC, it is only a sufficient condition for SPR. In addition, it only involves the single-view data.

Comparison to [You and Vidal, 2015]. In [You and Vidal, 2015], the authors show that the sparse representation models BP [Chen et al., 1998] and OMP [Pati et al., 1993] can yield subspace-preserving representation (SPR) under the following principal recovery condition (PRC)

where r (K (±Ak)) is defined as the radius of the largest ball inscribed in K(±Ak), which denotes the convex hull of the symmetrized columns of Ak. Here R(Ak) denotes the range of Ak, i.e., the linear span of columns of Ak. The incoherence µ (A-k, R(Ak)) is defined as

While the authors developed the dual recovery condition (DRC) to relax PRC, both DRC and PRC are only sufficient conditions and are confined to single-view data.

Comparison to [Kaba et al., 2021]. In [Kaba et al., 2021], the authors also considers the SPR problem and derives a necessary and sufficient condition termed subspace nullspace property (SNSP) for SPR. Specifically, the SNSP is defined as follows.

Definition 8. Let P := {Pi}Ki=1 be a partition of the index set {1, · · · ,N} and Null(A) be the nullspace of A. Denote a subset of Null(A) w.r.t. (with respect to) P by

The dictionary matrix A satisfies the SNSP if and only if for any η ∈ Null(A, P) and P ∈ P, there holds

where P c denotes the complement set of P.

Compared with SNSP, the proposed ARP in Definition 5 is more concise and intuitive. Furthermore, the work [Kaba et al., 2021] is restricted to single-view data and cannot be applied for multi-view data. In comparison, our results can apply to both single-view and multi-view data.

Comparison to [Thaker et al., 2022]. The work [Thaker et al., 2022] considers the problem of reverse engineering adversarial attacks and poses it as a block sparse recovery (BSR) problem. There are several key differences between our work and the work [Thaker et al., 2022]. Firstly, our theory is devised for multi-view data while [Thaker et al., 2022] is for single-view data, which can not be directly applied for multiview data. Secondly, the main results in Theorem 1 and 2 in our paper is both necessary and sufficient condition for multi-view subspace-preserving recovery while the core results in [Thaker et al., 2022] are only sufficient for singleview subspace-preserving recovery. Thirdly, the results in

[Thaker et al., 2022] requires the data labels in advance while our results do not depend on such supervised information.

Based on the analysis above, we can draw the conclusion that our theoretical results for MSPR are novel and meaningful compared to prior works.

4 Application toMulti-view Subspace Clustering

Consider the Multi-view Sparse Subspace Clustering (MSSC) model [Wang et al., 2023]

where Ci(i, :) is the i-th row of the matrix Ci. Let C∗i be the optimal solution of (32) for i = 1, · · · ,N. We first construct the common representation matrix C∗ ∈ RN×N such that

for i = 1, · · · ,N. Then we construct the affinity matrix W = |C∗ | + ∣∣(C∗ )T ∣∣. Finally, we apply the spectral clustering algorithm to the affinity matrix and obtain the final clustering results. A desirable affinity matrix W should satisfy the following subspace-preserving property: Wij ̸= 0 only if the i-th sample and the j-th sample are from the same cluster.

Theorem 4. The affinity matrix W generated by the MSSC model (32) satisfies the subspace-preserving property if and only if the leave-one-out multi-view data ˙X\ ˙xi satisfies the ARP for i = 1, · · · ,N.

Proof. Assume that ˙X\ ˙xi satisfies the ARP. According to Theorem 1, for each sample {xvi }Vv=1 , the representation matrix C∗i is a MSPR, i.e., supprow(C∗i ) ⊂ Ik. It follows from Eq. (33) that each column C∗ (:, i) of C∗ is also subspace preserving, i.e., C∗ (j, i) ̸= 0 only if xvi and xvj are from the same subspace for each view. According to the construction of the affinity matrixW, Wij ̸= 0 only if i-th sample and the j-th sample are from the same cluster. Thus, W satisfies the subspace-preserving property and completes the proof.

5 Application toMulti-view Subspace Classification

Given any newmulti-view test sample ˙y ∈ ˙ Sk\{˙0}, theMSC (Multi-view Subspace Classification) method [Shekhar et al.,

2013] first computes the representation matrix of ˙y using the following JSR model

where ˙D denotes the multi-view training data. Then for each class the reconstruction residual is calculated as

where δk(C(:, v)) ∈ RN denotes the vector containing the entries associated with the k-th class and changing the remaining entries as zeros.

Theorem 5. MSC is guaranteed to succeed to classify any newmulti-view test sample ˙y ∈ ˙ Sk\{˙0} for any class k if the multi-view training data ˙D satisfy the ARP property.

Proof. According to Theorem 1, the representation matrix C∗ of the test sample ˙y ∈ ˙ Sk\{ ˙0} is a MSPR, i.e., C∗ (I-k, : ) = 0. It follows that

According to Eq. (35), the reconstruction residual of each class is rk( ˙y) = ∑Vv=1 ∥yv - Dv δk(C(:, v))∥2 = 0, and rl( ˙y) = ∑Vv=1 ∥yv -Dv δl(C(:, v))∥2 = ∑Vv=1 ∥yv ∥2, l ̸= k. Since rk( ˙y) < minl̸=k rl( ˙y), the test sample is assigned to the correct class k.

6 Conclusions

This paper studies the multi-view subspace-preserving recovery theory, which plays a critical role for multi-view subspace clustering and classification. We first generalize the atomic norm to multi-view data and define the Multi-view Atomic Norm (MAN). Based on MAN, we derived a necessary and sufficient condition dubbed ARP (Atomic Recovery Property) for the JSR model to produce MSPR. To the best of our knowledge, ARP is the first necessary and sufficient theoretical condition for multi-view subspace-preserving recovery. The results reveal important geometric sights and provide theoretical justification for the success of multi-view subspace clustering and classification.

Acknowledgments

We are grateful to the anonymous IJCAI reviewers for their constructive comments. This work was supported by the National Natural Science Foundation of China (under Grant Nos. 62076041, 62276111, 61702057, 12071166, 62376104 and 62172458), the Fundamental Research Funds for the Central Universities of China (under Grant Nos. 2662023XXPY002 and 2662023LXPY005), the HZAUAGIS Cooperation Fund (under Grant No. SZYJY2023010), and the Industry-University-Research Cooperation Project of Zhuhai, Guangdong, China, under Grant GP/026/2020 and Grant HF-010-2021.