--- title: "Atomic Recovery Property for Multi-view Subspace-Preserving Recovery" authors: - "Yulong Wang" doi: "10.24963/ijcai.2024/569" url: "https://ijcai.org/proceedings/2024/569" pdf: "https://ijcai.org/proceedings/2024/0569.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "5144-5152" track: "Main Track" keywords: - "Machine Learning: ML: Multi-view learning" - "Machine Learning: ML: Matrix/tensor methods" - "Machine Learning: ML: Classification" - "Machine Learning: ML: Clustering" --- # Atomic Recovery Property for Multi-view Subspace-Preserving Recovery Yulong Wang *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 5144-5152. DOI: [10.24963/ijcai.2024/569](https://doi.org/10.24963/ijcai.2024/569) ## Abstract As the theoretical underpinnings for subspace clustering and classification, subspace-preserving recovery has attracted intensive attention in recent years. However, previous theoretical advances for subspace-preserving recovery only focus on the single-view data and most of them are based on conditions that are only sufficient. In this paper, we propose a necessary and sufficient condition referred to as Atomic Recovery Property (ARP) for multi-view subspace-preserving recovery. To this end, we generalize the atomic norm from single-view data to multi-view data and define the Multi-view Atomic Norm (MAN). Our another contribution is to provide a geometrically more interpretable characterization of ARP with respect to the unit ball of MAN. Based on the proposed multi-view subspace-preserving recovery theory, we also derive novel theoretical results for multi-view subspace clustering and classification, respectively. ## Full text ## 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. Table 1: Key notations used in this paper. | Notation | Description | |-------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | x, x, X, X N [N ] V K dv S v k ⊂ Rdv ˙ Sk Av ∈ Rdv×N Av ˙A Ik ⊂ [N] I-k ⊂ [N] | scalar, vector, matrix, set number of samples set of integers from 1 to N number of views number of classes data dimension of the v-th view the k-th subspace in the v-th view {S v k , ∀v ∈ [V ]} data matrix of the v-th view set of columns of Av and -Av {Av , ∀v ∈ [V ]} index set of samples in the k-th class index set of samples out of the k-th class | ## 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 Table 2: Comparison of different related works. Here "Sufficient" and "Necessary" mean whether the theoretical conditions in the corresponding works are sufficient and necessary, respectively. | References | Year | Task | Model | Sufficient | Necessary | Multi-view | |------------------------------------|--------|----------------|---------|--------------|-------------|--------------| | [Soltanolkotabi and Cand´es, 2012] | 2012 | Clustering | BP | ✓ | × | × | | [Dyer et al., 2013] | 2013 | Clustering | OMP | ✓ | × | × | | [You and Vidal, 2015] | 2015 | Recovery | BP&OMP | ✓ | × | × | | [You et al., 2016] | 2016 | Clustering | OMP | ✓ | × | × | | [Wang et al., 2019] | 2019 | Classification | AR | ✓ | × | × | | [Kaba et al., 2021] | 2021 | Recovery | BP | ✓ | ✓ | × | | [Thaker et al., 2022] | 2022 | Recovery | BSP | ✓ | × | × | | This paper | 2024 | Recovery | JSR | ✓ | ✓ | ✓ | [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. ## References 1. [Abavisani and Patel, 2018] Mahdi Abavisani and Vishal M Patel. Deep multimodal subspace clustering networks. IEEE J. Sel. Top. Signal Process., 12(6):1601-1614, 2018. 2. [Bahrampour et al., 2015] Soheil Bahrampour, Nasser M Nasrabadi, Asok Ray, and William Kenneth Jenkins. Mul- timodal task-driven dictionary learning for image classifi- cation. IEEE Trans. Image Process., 25(1):24-38, 2015. 3. [Chandrasekaran et al., 2012] Venkat Chandrasekaran, Ben- jamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational mathematics, 12(6):805-849, 2012. 4. [Chen et al., 1998] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33, 1998. 5. [Chen et al., 2023] Zhe Chen, Xiao-Jun Wu, Tianyang Xu, and Josef Kittler. Fast self-guided multi-view subspace clustering. IEEE Trans. Image Process., 32:6514-6525, 2023. 6. [Dyer et al., 2013] Eva L Dyer, Aswin C Sankaranarayanan, and Richard G Baraniuk. Greedy feature selection for sub- space clustering. The Journal of Machine Learning Re- search, 14(1):2487-2517, 2013. 7. [Elhamifar and Vidal, 2009] Ehsan Elhamifar and René Vi- dal. Sparse subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2790-2797, 2009. 8. [Elhamifar and Vidal, 2010] Ehsan Elhamifar and René Vi- dal. Clustering disjoint subspaces via sparse represen- tation. In Proc. IEEE Conf. ICASSP, pages 1926-1929, 2010. 9. [Elhamifar and Vidal, 2013] Ehsan Elhamifar and René Vi- dal. Sparse subspace clustering: algorithm, theory, and applications. IEEE Trans. Pattern Anal. Mach. Intell., 35(11):2765-2781, Nov. 2013. 10. [Foucart and Rauhut, 2013] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Springer Science & Business Media, 2013. 11. [Guo et al., 2022] Jipeng Guo, Yanfeng Sun, Junbin Gao, Yongli Hu, and Baocai Yin. Logarithmic schatten-p p norm minimization for tensorial multi-view subspace clustering. IEEE Trans. Pattern Anal. Mach. Intell., 45(3):3396-3410, 2022. 12. [Kaba et al., 2021] Mustafa D Kaba, Chong You, Daniel P Robinson, Enrique Mallada, and Rene Vidal. A nullspace property for subspace-preserving recovery. In Interna- tional Conference on Machine Learning, pages 5180- 5188, 2021. 13. [Li et al., 2019] Ruihuang Li, Changqing Zhang, Qinghua Hu, Pengfei Zhu, and Zheng Wang. Flexible multi-view representation learning for subspace clustering. In IJCAI, pages 2916-2922, 2019. 14. [Pati et al., 1993] Yagyensh Chandra Pati, Ramin Rezaiifar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and comput- ers, pages 40-44 vol.1, Nov. 1993. 15. [Ren et al., 2022] Hengyi Ren, Lijuan Sun, Jian Guo, and Chong Han. A dataset and benchmark for multimodal biometric recognition based on fingerprint and finger vein. IEEE Trans. Inf. Forensics Secur., 17:2030-2043, 2022. 16. [Shekhar et al., 2013] Sumit Shekhar, Vishal M Patel, Nasser M Nasrabadi, and Rama Chellappa. Joint sparse representation for robust multimodal biometrics recogni- tion. IEEE Transactions on pattern analysis and machine intelligence, 36(1):113-126, 2013. 17. [Soltanolkotabi and Candés, 2012] Mahdi Soltanolkotabi and Emmanuel J Candés. A geometric analysis of subspace clustering with outliers. The Annals of Statistics, 40(4):2195-2238, 2012. 18. [Tang and Liu, 2022] Huayi Tang and Yong Liu. Deep safe incomplete multi-view clustering: Theorem and algo- rithm. In International Conference on Machine Learning, pages 21090-21110, 2022. 19. [Thaker et al., 2022] Darshan Thaker, Paris Giampouras, and René Vidal. Reverse engineering ℓ p attacks: A block- sparse optimization approach with recovery guarantees. In International Conference on Machine Learning, pages 21253-21271, 2022. 20. [Tsakiris and Vidal, 2018] Manolis Tsakiris and Rene Vidal. Theoretical analysis of sparse subspace clustering with missing entries. In International Conference on Machine Learning, pages 4975-4984, 2018. 21. [Vidal, 2011] René Vidal. Subspace clustering. IEEE Signal Process. Mag., 28(2):52-68, Mar. 2011. 22. [Wang and Xu, 2016] Y. Wang and H. Xu. Noisy sparse sub- space clustering. J. Mach. Learn. Res., 17(12):1-41, 2016. 23. [Wang et al., 2019] Yulong Wang, Yuan Yan Tang, Luoqing Li, Hong Chen, and Jianjia Pan. Atomic representation- based classification: theory, algorithm, and applications. IEEE transactions on pattern analysis and machine intel- ligence, 41(1):6-19, 2019. 24. [Wang et al., 2023] Yulong Wang, Kit Ian Kou, Hong Chen, Yuan Yan Tang, and Luoqing Li. Simultaneous robust matching pursuit for multi-view learning. Pattern Recog- nition, 134:109100, 2023. 25. [Wright et al., 2009] John Wright, Allen Y Yang, Arvind Ganesh, S Shankar Sastry, and Yi Ma. Robust face recog- nition via sparse representation. IEEE Trans. Pattern Anal. Mach. Intell., 32(2):210-227, Jan. 2009. 26. [You and Vidal, 2015] Chong You and René Vidal. Geomet- ric conditions for subspace-sparse recovery. In Interna- tional conference on machine learning, pages 1585-1593. 27. PMLR, 2015. 28. [You et al., 2016] Chong You, Daniel Robinson, and René Vidal. Scalable sparse subspace clustering by orthogonal matching pursuit. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3918- 3927, 2016. 29. [Zhang et al., 2017] Heng Zhang, Vishal M Patel, and Rama Chellappa. Low-rank and joint sparse representations for multi-modal recognition. IEEE Transactions on Image Processing, 26(10):4741-4752, 2017. 30. [Zhang et al., 2021] Shangzhi Zhang, Chong You, René Vi- dal, and Chun-Guang Li. Learning a self-expressive net- work for subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12393-12403, 2021.