Consistency of regularized spectral clustering

Clustering is a widely used technique in machine learning, however, relatively little research in consistency of clustering algorithms has been done so far. In this paper we investigate the consistency of the regularized spectral clustering algorithm, which has been proposed recently. It provides a natural out-of-sample extension for spectral clustering. The presence of the regularization term makes our situation different from that in previous work. Our approach is mainly an elaborate analysis of a functional named the clustering objective. Moreover, we establish a convergence rate. The rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers. Some new methods are exploited for the analysis since the underlying setting is much more complicated than usual. Some new methods are exploited for the analysis since the underlying setting is much more complicated than usual.     

Neighbourhood preserving discriminant embedding in face recognition

In this paper, we present an effective technique on discriminative feature extraction for face recognition. The proposed technique incorporates Graph Embedding and the Fisher’s criterion where we call it as Neighbourhood Preserving Discriminant Embedding (NPDE). Utilizing the Graph Embedding criterion, the underlying nonlinear face data structure is revealed as representative and discriminative features for analysis. We employ Neighbourhood Preserving Embedding (NPE) for the purpose. NPE takes into account the restriction that neighbouring points in the high-dimensional space must remain within the same neighbourhood in the low dimension space and be located in a similar relative spatial situation (without changing the local structure of the nearest neighbours of each data point). Furthermore, by taking the advantage of the Fisher’s criterion, the discriminating power of NPDE is further boosted. Based on this intuition, NPDE obtains better discriminative capability and experimentally verified in ORL, PIE and FRGC.     

On some colorings of a double graph

In this note, we present some results concerning the chromatic index, the total chromatic index, the adjacent vertex distinguishing chromatic index and the adjacent vertex distinguishing total chromatic index for double graphs. In particular, we study the double graphs of class 1 and of type 1.     

Factorizations of complete graphs into caterpillars of diameter 5

We examine factorizations of complete graphs K_2n into caterpillars of diameter 5. First we present a construction generalizing some previously known methods. Then we use the new method along with some previous partial results to give a complete characterization of caterpillars of diameter 5, which factorize the complete graph K_2n.     

A generalization of the Erdös-Ko-Rado theorem

In this note, we investigate some properties of local Kneser graphs defined in [János Körner, Concetta Pilotto, Gábor Simonyi, Local chromatic number and sperner capacity, J. Combin. Theory Ser. B 95 (1) (2005) 101-117]. In this regard, as a generalization of the Erdös-Ko-Rado theorem, we characterize the maximum independent sets of local Kneser graphs. Next, we provide an upper bound for their chromatic number.     

Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.     

Segmentation of synthetic aperture radar image using multiscale information measure-based spectral clustering

A multiscale information measure （MIM）, calculable from per-pixel wavelet coefficients, but relying on global statistics of synthetic aperture radar （SAR） image, is proposed. It fully exploits the variations in speckle pattern when the image resolution varies from course to fine, thus it can capture the intrinsic texture of the scene backscatter and the texture due to speckle simultaneously. Graph spectral segmen- tation methods based on MIM and the usual similarity measure are carried out on two real SAR images. Experimental results show that MIM can characterize texture information of SAR image more effectively than the commonly used similarity measure.