Abstract Most existing approaches address multi-view subspace clustering problem by constructing the affinity matrix on each view separately and afterwards propose how to extend spectral clustering algorithm to handle multi-view data. This paper presents an approach to multi-view subspace clustering that learns a joint subspace representation by constructing affinity matrix shared among all views. Relying on the importance of both low-rank and sparsity constraints in the construction of the affinity matrix, we introduce the objective that balances between the agreement across different views, while at the same time encourages sparsity and low-rankness of the solution. Related low-rank and sparsity constrained optimization problem is for each view solved using the alternating direction method of multipliers. Furthermore, we extend our approach to cluster data drawn from nonlinear subspaces by solving the corresponding problem in a reproducing kernel Hilbert space. The proposed algorithm outperforms state-of-the-art multi-view subspace clustering algorithms on one synthetic and four real-world datasets.
Denote the SVD of @math as @math . The minimizer of equation ) is uniquely given by @cite_17 : In the cases when data is contaminated by noise, the following problem needs to be solved: The optimal solution of equation ) has been derived in @cite_20 : where @math , @math and @math . Matrices are partitioned according to the sets @math and @math .
@cite_20 @cite_17
2081956522 2114147096 2077306951 1480169421
An algorithm for solving the problem: minimize @math (a convex function) subject to @math , @math , each @math a concave function, is presented. Specifically, the function [ P [ x,t,r_k ] f( x ) + r_k^ - 1 [ g_i ( x ) - t_i ] ^2 ] is minimized over all x, nonnegative t, for a strictly decreasing null sequence @math . This extends the work of T. Pietrzykowski [5]. It is proved that for every @math , there exists a finite point @math which minimizes P, and which solves the convex programming problem as @math . This algorithm is similar to the Sequential Unconstrained Minimization Technique (SUMT) [1] in that it solves the (Wolfe) dual programming problem [6]. It differs from SUMT in that (1) it approaches the optimum from the region of infeasibility (i.e., it is a relaxation technique), (2) it does not require a nonempty interior to the nonlinearly constrained region, (3) no separate feasibilit... We consider inexact linear equations y ≈ Φx where y is a given vector in R n , Φ is a given n x m matrix, and we wish to find x 0,∈ as sparse as possible while obeying ∥y - Φx 0,∈ ∥ 2 ≤ ∈. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the l 1 -minimization problem min ∥x∥ 1 subject to ∥y - Φx∥ 2 ≤ e is convex and is considered tractable. We show that for most Φ, if the optimally sparse approximation x 0,∈ is sufficiently sparse, then the solution x 1,∈ of the l 1 -minimization problem is a good approximation to x 0,∈ . We suppose that the columns of Φ are normalized to the unit l 2 -norm, and we place uniform measure on such Φ. We study the underdetermined case where m ∼ τn and τ > 1, and prove the existence of p = p(r) > 0 and C = C(p, τ) so that for large n and for all Φ's except a negligible fraction, the following approximate sparse solution property of Φ holds: for every y having an approximation ∥y - Φx 0 ∥ 2 ≤ ∈ by a coefficient vector x 0 e R m with fewer than ρ · n nonzeros, ∥x 1,∈ - x 0 ∥ 2 ≤ C ≤ ∈. This has two implications. First, for most Φ, whenever the combinatorial optimization result x 0,∈ would be very sparse, x 1,∈ is a good approximation to x 0,∈ . Second, suppose we are given noisy data obeying y = Φx 0 + z where the unknown x 0 is known to be sparse and the noise ∥z∥ 2 ≤ ∈. For most Φ, noise-tolerant l 1 -minimization will stably recover x 0 from y in the presence of noise z. We also study the barely determined case m = n and reach parallel conclusions by slightly different arguments. Proof techniques include the use of almost-spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices. We consider the problem of estimating an unknown signal @math from noisy linear observations @math . In many practical instances, @math has a certain structure that can be captured by a structure inducing convex function @math . For example, @math norm can be used to encourage a sparse solution. To estimate @math with the aid of @math , we consider the well-known LASSO method and provide sharp characterization of its performance. We assume the entries of the measurement matrix @math and the noise vector @math have zero-mean normal distributions with variances @math and @math respectively. For the LASSO estimator @math , we attempt to calculate the Normalized Square Error (NSE) defined as @math as a function of the noise level @math , the number of observations @math and the structure of the signal. We show that, the structure of the signal @math and choice of the function @math enter the error formulae through the summary parameters @math and @math , which are defined as the Gaussian squared-distances to the subdifferential cone and to the @math -scaled subdifferential, respectively. The first LASSO estimator assumes a-priori knowledge of @math and is given by @math . We prove that its worst case NSE is achieved when @math and concentrates around @math . Secondly, we consider @math , for some @math . This time the NSE formula depends on the choice of @math and is given by @math . We then establish a mapping between this and the third estimator @math . Finally, for a number of important structured signal classes, we translate our abstract formulae to closed-form upper bounds on the NSE. One of the current challenges in underwater acoustic array signal processing is the detection of quiet targets in the presence of noise. In order to enable robust detection, one of the key processing steps requires data and replica whitening. This, in turn, involves the eigen-decomposition of the sample spectral matrix, C x = 1 over K Σ x KX(k)XH(k) where X(k) denotes a single frequency snapshot with an element for each element of the array. By employing the singular value decomposition (SVD) method, the eigenvectors and eigenvalues can be determined directly from the data without computing the sample covariance matrix, reducing the computational requirements for a given level of accuracy (van Trees, Optimum Array Processing). (Recall that the SVD of a complex matrix A involves determining V, Σ, and U such that A = UΣVH where U and V are orthonormal and Σ is a positive, real, diagonal matrix containing the singular values of A. U and V are the eigenvectors of AAH and AHA, respectively, while the singular values are the square roots of the eigenvalues of AAH.) Because it is desirable to be able to compute these quantities in real time, an efficient technique for computing the SVD is vital. In addition, emerging multicore processors like graphical processing units (GPUs) are bringing parallel processing capabilities to an ever increasing number of users. Since the computational tasks involved in array signal processing are well suited for parallelization, it is expected that these computations will be implemented using GPUs as soon as users have the necessary computational tools available to them. Thus, it is important to have an SVD algorithm that is suitable for these processors.