Search

The maximum weighted submatrix coverage problem is a recently introduced problem with applications in data mining. It is concerned with selecting K submatrices of a given numerical matrix such that the sum of the matrix-entries, which occur in at least one of the selected submatrices, is maximized. In the paper introducing the problem, a problem-specific constraint programming approach was developed and embedded in a large neighborhood-search to obtain a heuristic. A compact integer linear programming formulation was also presented, but deemed inefficient due to its size. In this paper, we introduce new integer linear programming formulations for the problem, one of them is based on Benders decomposition. The obtained Benders decomposition-based formulation has a nice combinatorial structure, i.e., there is no need to solve linear programs to separate Benders cuts. We present preprocessing procedures and valid inequalities for all formulations. We also develop a greedy randomized adaptive search procedure for the problem, which is enhanced with a local search. A computational study using the instances from literature is done to evaluate the effectiveness of our new approaches. Our algorithms manage to find improved primal solutions for ten out of 17 real-world instances, and optimality is proven for two real-world instances. Moreover, for over 700 of 1617 large-scale synthetic instances, our algorithms find improved primal solutions compared to the heuristics from the literature.

Multi-view subspace clustering is an effective method to partition data into their corresponding categories. Nevertheless, existing multi-view subspace clustering approaches generally operate in a purely unsupervised manner, while ignoring the valuable weakly supervised information that can be readily obtained in many practical applications. In this paper, we consider the weakly supervised form of sample pair constraints, and devote to promoting the performance of multi-view subspace clustering with the aid of such prior knowledge. To achieve this goal, inspired by the intrinsic block diagonal structure of ideal low-rank representation (LRR), we propose a novel regularization to integrate must-link, cannot-link and normalization constraints into a unified formulation. The proposed regularization can be regarded as a general description for sample pairwise constraints, and thus provides a flexible framework for multi-view semi-supervised subspace clustering task. Furthermore, we devise a contrained tensor representation learning (CTRL) model that takes advantage of our proposed regularization to facilitate the learning of the desired representation tensor. An efficient optimization algorithm based on alternating direction minimization strategy is carefully designed to solve the proposed CTRL model. Extensive experiments on eight challenging real-world datasets are conducted, and the results validate the effectiveness of our designed pairwise constraints regularization, as well as the superiority of the proposed CTRL model.

This letter proposes a novel sparse recovery method of multiple-input and multiple-output (MIMO) radar compressed sensing (CS) imaging algorithms. This method leverages the prior structure of the measurement matrix to judge targets' locations and to estimate the sparsity level in the grid roughly and finally inhabits the emergence of false targets in the imaging figure. Explicitly, the algorithm we propose is inspired by the orthogonal matching pursuit (OMP) algorithm. First, the measurement matrix can be divided into some submatrices by column. Then, we estimate which submatrices do not contain signal components by the algorithms we propose in this literature to achieve the reconstruction of the measurement matrix. Finally, we use the sparse Bayesian learning algorithm and the sparsity adaptive matching pursuit algorithm to recover the target location and scattering intensity. Experiments validate that the reconstruction error of the algorithm we propose is much lower than other sparse recovery algorithms, and targets in the imaging are more obvious than other algorithms.

Resistive random access memory (RRAM) has been demonstrated to implement multiply-and-accumulate (MAC) operations using a highly parallel analog fashion, which dramatically accelerates the convolutional neural networks (CNNs). Since CNNs require considerable converters between analog crossbars and digital peripheral circuits, recent studies map the binary neural networks (BNNs) onto RRAM and binarize the weights to {+1, −1}. However, two mainstream representations for BNN weights introduce patterns of redundant 0s and 1s when dealing with negative weights. In this work, we reduce the area of redundant 0s and 1s by proposing a BNN weight representation framework based on the novel pattern representation and a corresponding architecture. First, we spilt the weight matrix into several small matrices by clustering adjacent columns together. Second, we extract 1s’ patterns, i.e., the submatrices only containing 1s, from the small weight matrix, such that each final output can be represented by the sum of several patterns. Third, we map these patterns onto RRAM crossbars, including pattern computation crossbars (PCCs) and pattern accumulation crossbars (PACs). Finally, we compare the pattern representation with two mainstream representations and adopt the more area efficient one. The evaluation results demonstrate that our framework can save over 20% of crossbar area effectively, compared with two mainstream representations.

This paper is concerned with the identification of the bilinear systems in the state-space form. The parameters to be identified of the considered systems are coupled with the unknown states, which makes the identification problem difficult. To deal with such a difficulty, the iterative estimation theory is considered to derive the joint parameter and state estimation algorithm. Specifically, a moving data window least squares-based iterative (MDW-LSI) algorithm is derived to estimate the parameters of the systems by using the window data, and the unknown states are estimated by a bilinear state estimator. Furthermore, in order to improve the computational efficiency, a matrix decomposition-based MDW-LSI algorithm and a hierarchical MDW-LSI algorithm are developed according to the block matrix inversion lemma and the hierarchical identification principle. Finally, the computational efficiency is discussed and the numerical examples are employed to test the proposed approaches.

Structured representation is of remarkable significance in subspace clustering. However, most of the existing subspace clustering algorithms resort to single-structured representation, which may fail to fully capture the essential characteristics of data. To address this issue, a novel multi-structured representation subspace clustering algorithm called block diagonal sparse representation (BDSR) is proposed in this paper. It takes both sparse and block diagonal structured representations into account to obtain the desired affinity matrix. The unified framework is established by integrating the block diagonal prior into the original sparse subspace clustering framework and the resulting optimization problem is iteratively solved by the inexact augmented Lagrange multipliers (IALM). Extensive experiments on both synthetic and real-world datasets well demonstrate the effectiveness and efficiency of the proposed algorithm against the state-of-the-art algorithms.

In control engineering, numerical stability and real time are the two most important requirements for the matrix inversion. This article presents an efficient and robust method for the field-programmable gate array (FPGA) calculation of the matrix inversion. We initially consider the scenario that the matrix to be processed is a nonsingular Hermitian matrix. The proposed computation procedures are composed of the matrix decomposition, triangular matrix inversion, and matrices multiplication. The first procedure is completed by LDL factorization based on the outer form of Cholesky's method, whereas the recursive algorithm for block submatrices is adopted to achieve the triangular matrix inversion. The new method has the high level in the parallel pipelining mechanism and steals the characteristics of both the upper triangular matrix and its inversion to reduce the computation load and improve the numerical stability. Furthermore, the non-Hermitian matrix inversion can be easily solved if another procedure is added in the new method. Finally, we compare our method with the exiting FPGA-based techniques on one Xilinx Virtex-7 XC7VX690T FPGA. Meanwhile, it has solved one array antenna control problem of the adaptive digital beam forming for one phased array radar successfully.

The kernel subspace clustering algorithm aims to tackle the nonlinear subspace model. The block diagonal representation subspace clustering has a more promising capability in pursuing the k-block diagonal matrix. Therefore, the low-rankness and the adaptivity of the kernel subspace clustering can boost the clustering performance, so an adaptive low-rank kernel block diagonal representation (ALKBDR) subspace clustering algorithm is put forward in this work. On the one hand, for the nonlinear nature of the practical visual data, a kernel block diagonal representation (KBDR) subspace clustering algorithm is put forward. The proposed KBDR algorithm first maps the original input space into the kernel Hilbert space which is linearly separable, and next applies the spectral clustering on the feature space. On the other hand, the ALKBDR algorithm uses the adaptive kernel matrix and makes the feature space low-rank to further promote the clustering performance. The experimental results on the Extended Yale B database and the ORL dataset have proved the excellent quality of the proposed KBDR and ALKBDR algorithm in comparison with other advanced subspace clustering algorithms that also are tested in this paper.

In the mechanical design industry, it is very time-consuming to convert actual engineering design problems into finite element models, and it is repeatedly modified during the product design process. Each time the structure is modified, computer simulation analysis is repeated, and the product development cycle becomes longer. Therefore, in this paper, a re-analysis theoretical method based on the inversion of the block matrix based on the change threshold is proposed to quickly obtain responses with different accuracy after the structure is modified according to the initial analysis. By modifying the size of the change threshold, the accuracy and calculation time of the reanalysis results are controlled. This reanalysis method shortens a lot of calculation time under the premise of controllable response accuracy. In this paper, numerical calculations are given to show the accuracy of the response under different thresholds, and the efficiency of this method is proved by the finite element model under the same accuracy.

RNA molecules play crucial roles in various biological processes. Their three-dimensional configurations determine the functions and, in turn, influences the interaction with other molecules. RNAs and their interaction structures, the so-called RNA–RNA interactions, can be abstracted in terms of secondary structures, i.e., a list of the nucleotide bases paired by hydrogen bonding within its nucleotide sequence. Each secondary structure, in turn, can be abstracted into cores and shadows. Both are determined by collapsing nucleotides and arcs properly. We formalize all of these abstractions as arc diagrams, whose arcs determine loops. A secondary structure, represented by an arc diagram, is pseudoknot-free if its arc diagram does not present any crossing among arcs otherwise, it is said pseudoknotted. In this study, we face the problem of identifying a given structural pattern into secondary structures or the associated cores or shadow of both RNAs and RNA–RNA interactions, characterized by arbitrary pseudoknots. These abstractions are mapped into a matrix, whose elements represent the relations among loops. Therefore, we face the problem of taking advantage of matrices and submatrices. The algorithms, implemented in Python, work in polynomial time. We test our approach on a set of 16S ribosomal RNAs with inhibitors of Thermus thermophilus, and we quantify the structural effect of the inhibitors.

Subspace clustering is a technique utilized to find clusters within multiple subspaces. However, most existing methods cannot obtain an accurate block diagonal clustering structure to improve clustering performance. This drawback exists because these methods learn the similarity matrix in advance by utilizing a low dimensional matrix obtained directly from the data, where two unrelated data samples can stay related easily due to the influence of noise. This paper proposes a novel method based on coupled low-rank representation to tackle the above problem. First, our method constructs a manifold recovery structure to correct inadequacy in the low-rank representation of data. Then it obtains a clustering projection matrix that obeys the k-block diagonal property to learn an ideal similarity matrix. This similarity matrix denotes our clustering structure with a rank constraint on its normalized Laplacian matrix. Therefore, we avoid k-means spectral post-processing of the low dimensional embedding matrix, unlike most existing methods. Furthermore, we couple our method to allow the clustering structure to adaptively approximate the low-rank representation so as to find more optimal solutions. Several experiments on benchmark datasets demonstrate that our method outperforms similar state-of-the-art methods in Accuracy, Normalized Mutual Information, F-score, Recall, Precision, and Adjusted Rand Index evaluation metrics.

A simplified decoding method for polar codes with large kernels is presented. The proposed approach consists in decoder-side substitution of some submatrices of the polarizing transformation with matrices, which admit simpler evaluation of log-likelihood ratios. This approach enables complexity reduction for the successive cancellation, list and sequential decoding algorithms.

In recent years, the matrix enhancement and matrix pencil method (MEMP) as well as the forward-backward MEMP (FBMEMP) have been successfully applied to reduce the number of antenna elements in the single-pattern planar arrays. This article aims to extend the MEMP and FBMEMP to the synthesis of sparse planar arrays with multiple patterns. The generalized MEMP (GMEMP) first constructs an enhanced matrix for each target pattern according to their data samples, respectively, and then these enhanced matrices are used to form a composite Hankel block matrix. After that, two sets of poles corresponding to two sets of reconstructed location coordinates can be extracted from the principal eigenvectors of the composite Hankel block matrix by the matrix pencil method. The randomized singular value decomposition and Hankel matrix decomposition method are used to accelerate the above extraction process. Then, we make use of improved matching algorithm to pair the two sets of position coordinates to obtain 2-D coordinates. Finally, we use the least-square method to obtain the excitations of sparse planar array elements, which makes the reconstruction process of multiple patterns more stable and accurate. Apart from the above, the GMEMP is also extended to the synthesis of multiple shaped-beam patterns using the generalized forward-backward matrix enhancement and matrix pencil method (GFBMEMP). A series of representative numerical examples show that the proposed methods can reduce the number of elements in the planar arrays efficiently while maintaining the accuracy of all the patterns to be synthesized.

With the rapid emergence of data that can be described by different feature sets or different “views”, multi-view subspace clustering has attracted considerable research attention. To uncover the common latent structure shared by multiple views, existing models usually impose the sparse or/and low-rank constraint on the coefficients of each view data, and use Frobenius norm or l 1 -norm based metric to measure the residuals of multi-view data. However, the intuition behind the sparse or low-rank regularization is implicit. Besides, the Frobenius norm or l 1 -norm based metric is suitable to handle either Gaussian noise or sparse noise, which are very sensitive to larger noise or outliers. When the data is contaminated by large noise or densely corrupted, performance of existing models is degraded dramatically. In this article, we propose a novel multi-view subspace clustering method to provide superior robustness against large noise or outliers embedded in multi-view data. Our method adopts a more direct and intuitive block diagonal regularization to preserve the underlying structure of each view, and meantime introduces the cauchy loss function to deal with large noise. The derived consensus representation matrix can effectively preserve the underlying common structure of multi-view data and be robust to large noise and data corruptions. Experimental results show that our method outperforms the state-of-the-arts on both synthetic and real-world benchmark datasets.

Seismic data are usually contaminated by various noises. Noise suppression plays an important role in seismic processing. In this article, we propose a new denoising method based on the nonlocal weighted robust principal component analysis (RPCA). First, seismic data are divided into many patches and grouped based on the nonlocal similarity. For each group, then, we establish a similar block matrix and set up the objective function of the RPCA. Next, we introduce the iterative log-thresholding algorithm into the augmented Lagrangian method to solve the problem. Furthermore, varying weights are specified to different singular values when minimizing the objective function. Finally, aggregating all recovered matrices can obtain the denoised seismic data. The proposed method considers the nonlocal similarity and adaptively sets weights with local noise variance. It performs well also owing to the superiority of the iterative log-thresholding method. The presented method is assessed using a synthetic seismic section with several crossover events. We also apply this novel approach to a real seismic data, which shows good results. Comparison with other approaches reveals the effectiveness of the proposed approach.

This paper proposes a block encryption algorithm based on a new chaotic system that combines generative adversarial networks (GANs) and DNA sequence coding. First, the new one-dimensional chaotic system that combines GANs with DNA sequence coding generates two more complex key stream sequences. Then, the two different random sequences are combined with an improved Feistel network by utilizing the product of the block matrix to encrypt the image to scramble and diffuse the image. Finally, the security performance of this algorithm is quantitatively analysed. The simulation results show that the proposed chaotic system has a large key space, and the new algorithm yields adequate security and can resist exhaustive attacks and chosen-plaintext attacks. Therefore, this approach provides a new algorithm for secure transmission and protection of image information.

This paper presents three distributed techniques to find a sparse solution of the underdetermined linear problem $\textbf{g}=\textbf{Hu}$ with a norm-1 regularization, based on the Alternating Direction Method of Multipliers (ADMM). These techniques divide the matrix $\textbf{H}$ in submatrices by rows, columns, or both rows and columns, leading to the so-called consensus-based ADMM, sectioning-based ADMM, and consensus and sectioning-based ADMM, respectively. These techniques are applied particularly for millimeter-wave imaging through the use of a Compressive Reflector Antenna (CRA). The CRA is a hardware designed to increase the sensing capacity of an imaging system and reduce the mutual information among measurements, allowing an effective imaging of sparse targets with the use of Compressive Sensing (CS) techniques. Consensus-based ADMM has been proved to accelerate the imaging process and sectioning-based ADMM has shown to highly reduce the amount of information to be exchange among the computational nodes. In this paper, the mathematical formulation and graphical interpretation of these two techniques, together with the consensus and sectioning-based ADMM approach, are presented. The imaging quality, the imaging time, the convergence, and the communication efficiency among the nodes are analyzed and compared. The distributed capabitities of the ADMM-based approaches, together with the high sensing capacity of the CRA, allow the imaging of metallic targets in a 3D domain in quasi-real time with a reduced amount of information exchanged among the nodes.

Massive multiple-input multiple-output (M-MIMO) brings better robustness and spectral efficiency but higher computational challenges compared to small-scale MIMO. One of the key challenges is the large-scale matrix inversion, as widely employed in channel estimation and detection. Traditionally, to address the issue, several low-complexity matrix inversion methods have been proposed, including the tri-diagonal matrix approximation (TMA) and the Neumann-series approximation (NSA). Although the previous methods effectively alleviate the computational cost, they all fail to exploit the typical properties of channel matrices, leading to unsatisfactory error-rate performance in some non-ideal scenarios. To solve the issue, in this paper, a two-level and block diagonal based improved Neumann series approximation (TL-BD-INSA) algorithm is proposed, which is suitable for both ideal uncorrelated channels and the correlated channels with multiple-antenna user equipment (MAUE) system. First, a two-level block diagonal iteration based on matrix partition is employed, which exhibits performance comparable to the exact method while having a lower computational load. An improved normalization factor is then introduced to accelerate convergence. Numerical results show that, for $128\times 32$ MIMO with MAUE non-ideal channel, the proposed algorithm performs only 0.25 dB away from the exact matrix inversion when bit error rate (BER) $ = 10^{-3}$ . The implementation on Xilinx Virtex-7 FPGA and ASIC with TSMC 45 nm shows that the proposed detector can achieve 1731 bps/slices and 0.463 Gbps/mm $^2$ hardware efficiency, respectively, demonstrating that the proposed system can achieve a well trade-off between error performance and implementation efficiency.

In this paper, we propose an efficient algorithm to accelerate the existing Broad Learning System (BLS) algorithm for new added nodes. The existing BLS algorithm computes the output weights from the pseudoinverse with the ridge regression approximation, and updates the pseudoinverse iteratively. As a comparison, the proposed BLS algorithm computes the output weights from the inverse Cholesky factor of the Hermitian matrix in the calculation of the pseudoinverse, and updates the inverse Cholesky factor efficiently. Since the Hermitian matrix in the definition of the pseudoinverse is smaller than the pseudoinverse, the proposed BLS algorithm can reduce the computational complexity, and usually requires less than $\frac {2}{3}$ of complexities with respect to the existing BLS algorithm. Our experiments on the Modified National Institute of Standards and Technology (MNIST) dataset show that the speedups in accumulative training time and each additional training time of the proposed BLS over the existing BLS are 24.81%~ 37.99% and 36.45%~ 58.96%, respectively, and the speedup in total training time is 37.99%. In our experiments, the proposed BLS and the existing BLS both achieve the same testing accuracy when the tiny differences (≤ 0.05%) caused by the numerical errors are neglected, and the above-mentioned tiny differences and numerical errors become zeroes and ignorable, respectively, when the ridge parameter is not too small.

Context. The matrix notation is used to formalize the subject area within the framework of the algebraic approach. Effective computation of the discrete cosine transforms uses the reduction of a harmoniс basis to a block-cyclic matrix structure with the subsequent calculation of the transform using fast cyclic convolutions. An analysis of the structure of the basic block matrix of transforms provides a synthesis of algorithms of effective discrete cosine transforms of arbitrary sizes. The software implementation of the analysis of block-cyclic structures generates a description of the structure, which allows to reduce the computational complexity of the algorithm of effective discrete cosine transform and to perform parallelization of computation the cyclic convolutions.Objective. The work is to determine the algorithmic features of the analysis of the structure of a block-cyclic matrix containing integer arguments of basic harmonic functions, which will reduce the computational complexity of the synthesized discrete cosine transform algorithm based on cyclic convolutions.Method. Search and analysis by enumerating elements of the matrix with a variable step, taking into account the blockiness and cyclicity of the formed basis matrix of the discrete cosine transform, allows you to quickly analyze the structure of the block matrix of transform in comparison with full scanning.Results. Algorithmic and software for analyzing the structure of a block-cyclic basis matrix have been developed, with the help of which an array of data parameters for a formal description of the basis matrix structure of a discrete cosine transform is determined. The analysis of the structure of the base matrix allows us to determine the presence of identical cyclic submatrices placed horizontally or vertically relative to each other and, thereby, reduce the number of cycles of convolutions.Conclusions. An effective analysis of the block-cyclic structure of the basis matrix based on the developed software is an important part of the fast algorithm synthesis process, which provides a reduction in computational complexity and the ability to parallelize the implementation of the discrete cosine transform. The developed algorithmic and software for performing the analysis of the structure of a block-cyclic matrix can also be used to analyze the structure and search for the corresponding submatrices in any matrices with integer, real, and zero elements.

Mixed graphical models are widely implemented to capture interactions among different types of variables. To simultaneously learn the topology of multiple mixed graphical models and encourage common structure, people have developed a variational maximum likelihood inference approach, which takes advantage of the log-determinant relaxation. In this article, we further improve the computational efficiency of this method by exploiting the block diagonal structure of the solution. We present a simple necessary and sufficient condition to identify the connected components in the solution, so as to determine the block diagonal structure. Then, utilizing the idea of “divide-and-conquer”, we are able to adapt the joint structural inference problem for multiple related large sparse networks. We illustrate the merits of the proposed algorithm via experimental comparisons in computational speed.

Discriminative correlation filters (DCF) are efficient in visual tracking and have advanced the field significantly. However, the symmetry of correlation (or convolution) operator results in computational problems and does harm to the generalized translation equivariance. The former problem has been approached in many ways, whereas the latter one has not been well recognized. In this paper, we analyze the problems with the symmetry of circular convolution and propose an asymmetric one, which as a generalization of the former has a weak generalized translation equivariance property. With this operator, we propose a tracker called the asymmetric discriminative correlation filter (ADCF), which is more sensitive to translations of targets. Its asymmetry allows the filter and the samples to have different sizes. This flexibility makes the computational complexity of ADCF more controllable in the sense that the number of filter parameters will not grow with the sample size. Moreover, the normal matrix of ADCF is a block matrix with each block being a two-level block Toeplitz matrix. With this well-structured normal matrix, we design an algorithm for multiplying an N × N two-level block Toeplitz matrix by a vector with time complexity O(NlogN) and space complexity O(N), instead of O(N2). Unlike DCF-based trackers, introducing spatial or temporal regularization does not increase the essential computational complexity of ADCF. Comparative experiments are performed on a synthetic dataset and four benchmarks, including OTB-2013, OTB-2015, VOT-2016, and Temple-Color, and the results show that our method achieves state-of-the-art visual tracking performance.

Subspace clustering groups a set of data into their underlying subspaces according to the low-dimensional subspace structure of data. The performance of spectral clustering-based approaches heavily depends on the learned block diagonal structure of the affinity matrix. However, this structure is fragile in the presence of noise within data. As such, the clustering performance is degraded significantly. On the other hand, in practice, we often do not have a prior knowledge of error distribution at all, which results in that we cannot model the error with suitable norms. To this end, in this paper, we propose a robust block diagonal representation learning for subspace clustering. Specifically, a non-convex regularizer is directly utilized to constrain the affinity matrix for exploiting the block diagonal structure. Furthermore, we use a penalty matrix to adaptively weight the reconstruction error so that we can handle noise without prior knowledge. We also devise an effective method to compute the parameters related to this matrix, reducing the complexity of the parameter trains. Experimental results show that our method outperformed the state-of-the-art methods on both synthetic data and real-world datasets.

The algorithm for computing determinant of centrosymmetric matrix has been evaluated before. This algorithm shows the efficient computational determinant process on centrosymmetric matrix by working on block matrix only. One of block matrix at centrosymmetric matrix appearing on this algorithm is lower Hessenberg form. However, the other block matrices may possibly appear as block matrix for centrosymmetric matrix’s determinant. Therefore, this study is aimed to show the possible block matrices at centrosymmetric matrix and how the algorithm solve the centrosymmetric matrix’s determinant. Some numerical examples for different cases of block matrices on determinant of centrosymmetric matrix are given also. These examples are useful for more understanding for applying the algorithm with different cases.

Categorical regressor variables are usually handled by introducing a set of indicator variables, and imposing a linear constraint to ensure identifiability in the presence of an intercept, or equivalently, using one of various coding schemes. As proposed in Yuan and Lin (2006), the group lasso is a natural and computationally convenient approach to perform variable selection in settings with categorical covariates. As pointed out by Simon and Tibshirani (2012), “standardization” by means of block-wise orthonormalization of column submatrices each corresponding to one group of variables can substantially boost performance. In this note, we study the aspect of standardization for the special case of categorical predictors in detail. The main result is that orthonormalization is not required; column-wise scaling of the design matrix followed by re-scaling and centering of the coefficients is shown to have exactly the same effect. Similar reductions can be achieved in the case of interactions. The extension to the so-called sparse group lasso, which additionally promotes within-group sparsity, is considered as well. The importance of proper standardization is illustrated via simulations and a case study.

Multiple kernel clustering (MKC) has been intensively studied during the last few decades. Even though they demonstrate promising clustering performance in various applications, existing MKC algorithms do not sufficiently consider the intrinsic neighborhood structure among base kernels, which could adversely affect the clustering performance. In this paper, we propose a simple yet effective neighbor-kernel-based MKC algorithm to address this issue. Specifically, we first define a neighbor kernel, which can be utilized to preserve the block diagonal structure and strengthen the robustness against noise and outliers among base kernels. After that, we linearly combine these base neighbor kernels to extract a consensus affinity matrix through an exact-rank-constrained subspace segmentation. The naturally possessed block diagonal structure of neighbor kernels better serves the subsequent subspace segmentation, and in turn, the extracted shared structure is further refined through subspace segmentation based on the combined neighbor kernels. In this manner, the above two learning processes can be seamlessly coupled and negotiate with each other to achieve better clustering. Furthermore, we carefully design an efficient iterative optimization algorithm with proven convergence to address the resultant optimization problem. As a by-product, we reveal an interesting insight into the exact-rank constraint in ridge regression by careful theoretical analysis: it back-projects the solution of the unconstrained counterpart to its principal components. Comprehensive experiments have been conducted on several benchmark data sets, and the results demonstrate the effectiveness of the proposed algorithm.

The aim of the subspace clustering is to segment the high-dimensional data into the corresponding subspace. The structured sparse subspace clustering and the block diagonal representation clustering are quite advanced spectral-type subspace clustering algorithms when handling to the linear subspaces. In this paper, the respective advantages of these two algorithms are fully exploited, and the structured block diagonal representation (SBDR) subspace clustering is proposed. In many classical spectral-type subspace clustering algorithms, the affinity matrix which obeys the block diagonal property can not necessarily bring satisfying clustering results. However, the k-block diagonal regularizer of the SBDR algorithm directly pursues the block diagonal matrix, and this regularizer is obviously more effective. On the other hand, the general procedure of the spectral-type subspace clustering algorithm is to get the affinity matrix firstly and next perform the spectral clustering. The SBDR algorithm considers the intrinsic relationship of the two seemingly separate steps, the subspace structure matrix obtained by the spectral clustering is used iteratively to facilitate a better initialization for the representation matrix. The experimental results on the synthetic dataset and the real dataset have demonstrated the superior performance of the proposed algorithm over other prevalent subspace clustering algorithms.

In this paper, we propose a novel low-complexity, near-optimal soft-input soft-output detector for $\text {N}\times \text {M}$ multiple-input multiple-output (MIMO) systems. Our algorithm is based on the combination of minimum mean square error decision feedback equalization (MMSE-DFE) and conditional optimization. In a round-robin fashion, one symbol is detected using exhaustive search in such a way that all $\text {N}\times (\text {M}-1)$ submatrices of the baseband channel matrix are considered and the one with the best metric is chosen. This search over all columns of the channel matrix, which can be performed in parallel, has the advantages of improving the performance of the hard-output version of the detector, and refining the list of candidates for efficient implementation of the soft-output detector for MIMO systems with error correcting codes. In particular, it is shown that the error performance of the soft-output system is comparable to that of the list sphere decoder (LSD) but with much smaller list size, and hence smaller complexity than the latter. We also analyze the performance and complexity of the proposed algorithm and discuss different techniques to further reduce its complexity without affecting the performance. Finally, the obtained theoretical results are validated via simulations.

The theory of formal languages and, particularly, context-free grammars has been extensively studied and applied in different areas. For example, several approaches to the recognition and classification problems in bioinformatics are based on searching the genomic subsequences possessing some specific features which can be described by a context-free grammar. Therefore, the string-matching problem can be reduced to parsing – verification if some subsequence can be derived in this grammar. Such field of application as bioinformatics requires working with a large amount of data, so it is necessary to improve the existing parsing techniques. The most asymptotically efficient parsing algorithm that can be applied to any context-free grammar is a matrix-based algorithm proposed by Valiant. This paper aims to present Valiant’s algorithm modification, which main advantage is the possibility to divide the parsing table into successively computed layers of disjoint submatrices where each submatrix of the layer can be processed independently. Moreover, our approach is easily adapted for the string-matching problem. Our evaluation shows that the proposed modification retains all benefits of Valiant’s algorithm, especially its high performance achieved by using fast matrix multiplication methods. Also, the modified version decreases a large amount of excessive computations and accelerates the substrings searching.

A method for blind estimation of interleaver parameter was recently reported which made additional data from a limited amount of received data. However, the process of making additional data creates undesirable linearity which degrades estimation performance. Promise for improved estimation therefore lies in enhancing blind estimation of interleaver parameter without making additional data. In this paper, we propose an improved method to blindly estimate interleaver parameter under the condition of scant data. We first generate a matrix by using the received data. From this matrix we then make square submatrices and obtain their rank deficiency distribution. Finally, we estimate the interleaver parameter by comparing the rank deficiency distribution of the square submatrices and that of random binary matrices. Through computer simulations, we validate the proposed method in terms of detection probability and the number of false alarms. Simulation results show that the proposed method works better than the conventional method given scarce received data.

STMV beamforming algorithm needs inversion operation of matrix, and its engineering application is limited due to its huge computational cost. This paper proposed block iterative STMV algorithm based on one-phase regressive filter, matrix inversion lemma and inversion of block matrix. The computational cost is reduced approximately as 1/4 M times as original algorithm when array number is M. The simulation results show that this algorithm maintains high azimuth resolution and good performance of detecting multi-targets. Within 1 - 2 dB directional index and higher azimuth discrimination of block iterative STMV algorithm are achieved than STMV algorithm for sea trial data processing. And its good robustness lays the foundation of its engineering application.

In this article, we consider the estimation of angle of arrival (AoA) and angle of departure (AoD) for mmWave MIMO channels. For mmWave systems, there is typically a large number of antennas but limited radio frequency (RF) chains. The RF chain limitation indirectly restricts the effective number of antennas or the effective array size. In radar applications, it is known that a larger array size leads to more accurate AoA estimation or more resolvable paths. It is also known that with sparse arrays, which places antennas in a nonuniform sparse manner, an enlarged virtual array can be constructed when the sources are uncorrelated. We show that the idea of sparse arrays can also be used in mmWave systems to have augmented array sizes. The main difficulty in applying sparse arrays to mmWave MIMO channels lies in the fact the signals of different paths can be correlated in mmWave system, but uncorrelatedness is necessary for applying sparse array results. We show that the paths can be decorrelated by employing random precoders and combiners that are submatrices of banded Toeplitz matrices (SBT). When the precoder and combiner are SBT that are designed according to the antenna spacing of a sparse array, we can construct enlarged virtual transmit and receive arrays. With enlarged virtual arrays, accurate estimates can be obtained, as will be demonstrated by simulation examples.

A matrix-partitioned domain decomposition method based on integral equation using the out-of-core iterative solver is presented for accurately analyzing challenging electromagnetic scattering problems with limited memory. The proposed method is based on the domain decomposition strategy, which decomposes the original large complex matrix of the electrically large problem into several sub-matrices of the electrically small sub-problems. Then, the out-of-core solver is used to solve the partitioned matrix equation panel by panel. In the process of constructing sub-problems, the proposed method does not introduce any additional unknowns. Thus, it can significantly reduce memory consumption, expanding the scale of the problem that can be solved. Numerical examples demonstrate that the method is very accurate even for the EM scattering targets the RCS of which are below -40 dBsm. And it can completely eliminate the pseudo edge effect which often occurs in the implementation of the domain decomposition method. In addition, modeling and partitioning the subdomains of the proposed method is easy and flexible.

Standard methods of subspace clustering are based on self-expressiveness in the original data space, which states that a data point in a subspace can be expressed as a linear combination of other points. However, the real data in raw form are usually not well aligned with the linear subspace model. Therefore, it is crucial to obtain a proper feature space for performing high quality subspace clustering. Inspired by the success of Convolutional Neural Networks (CNN) for extraction powerful features from visual data and the block diagonal prior for learning a good affinity matrix from self-expression coefficients, in this paper, we propose a jointly trainable feature extraction and affinity learning framework with the block diagonal prior, termed as Convolutional Subspace Clustering Network with Block Diagonal prior (ConvSCN-BD), in which we solve the joint optimization problem in ConvSCN-BD via an alternating minimization algorithm, which updates the parameters in the convolutional modules and the self-expression coefficients with stochastic gradients descent and updates other variables with close-form solutions alternatingly. In addition, we derive the connection between the block diagonal prior and the subspace structured norm, and reveal that using the block diagonal prior on the affinity matrix is essentially incorporating the feedback information from spectral clustering. Experiments on three benchmark datasets demonstrated the effectiveness of our proposal.

In this paper we prove the strong consistency of several methods based on the spectral clustering techniques that are widely used to study the community detection problem in stochastic block models (SBMs). We show that under some weak conditions on the minimal degree, the number of communities, and the eigenvalues of the probability block matrix, the K-means algorithm applied to the eigenvectors of the graph Laplacian associated with its first few largest eigenvalues can classify all individuals into the true community uniformly correctly almost surely. Extensions to both regularized spectral clustering and degree-corrected SBMs are also considered. We illustrate the performance of different methods on simulated networks., 64 pages

Reducing the cost of implementing phasor measurement units (PMUs) can be achieved by determining the minimum number of devices needed to provide the electrical network observability. This article describes the optimal PMU placement algorithm, based on the analysis of the topological properties of the electrical network. It was shown that the optimal placement of PMUs can be achieved by dividing the nodal admittance matrix into four submatrices, one of them will be a band submatrix, which can be reduced to a lower triangular matrix of maximum rank by elementary transformations. Results reflecting the number of installed PMUs were obtained for IEEE test bus systems with 9, 14, 19, 30 and 57 nodes. For all test bus systems, the proposed PMU placement algorithm provides complete observability of the system with the same or fewer nodes of installation in comparison with the results of other authors. There were carried out computations with the help of the algorithm accelerated calculations of state estimation performance in power systems, in order to confirm the correctness of this approach. There were determined conditions under which the equations of nodal voltages were solved linearly and nonlinearly (iteratively).

In this paper, a fast direct solver based on strong admissibility skeletonization factorization (SASF) and Poggio-Miller-Chang-Harrington-Wu-Tsai (PMCHWT) is proposed for electromagnetic scattering from conducting objects. Different from weak admissibility skeletonization scheme, the proposed method constructs the sparse-data representation, in which interactions of well-separated groups are compressed by low-rank algorithm. As a result, the approximation rank is relatively small, and the computational efficiency will have significant improvement. Subsequently, SASF is applied to the compressed system matrix. The system matrix can be factorized into products of a series of block unit triangular matrices and a block diagonal matrix. The arising fill-in blocks corresponding to far-field interactions are compressed and eliminated by a novel and efficient method to maintain the high efficiency and accuracy of the factorization procedure. The computational complexity and storage requirement of proposed factorization scale as $O(N^{1.5})$ and $O(N\log N)$ , respectively. Several numerical results are presented to demonstrate the accuracy and effectiveness of the proposed method.

Distributed matrix computations over large clusters can suffer from the problem of slow or failed worker nodes (called stragglers) which can dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running 'coded' copies of tasks comprising a job; stragglers are typically treated as erasures. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Several practical matrix computation scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity. This is problematic as it results in significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. Furthermore, some MDS techniques also suffer from significant numerical stability issues. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments on Amazon Web Services (AWS) clusters support our findings.

In this paper, we propose a novel incomplete multi-view clustering method, in which a tensor nuclear norm regularizer elegantly diffuses the information of multi-view block-diagonal structure across different views. By exploring the membership between observed and missing samples and that between missing ones in each incomplete view with the guidance of the high-order view consistency, a global block-diagonal structure is well preserved in multiple spectral embedding matrices. Meanwhile, a consensus representation with strong separability is obtained for clustering. An iterative algorithm based on Augmented Lagrange Multiplier (ALM) is designed to solve the resultant model. Experimental results on six benchmark datasets indicate the superiority of the proposed method. http://github.com/ChangTang/TMBSD

Revealing data with intrinsically diagonal block structures is particularly useful for analyzing groups of highly correlated variables. Earlier researches based on non-negative matrix factorization (NMF) have been shown to be effective in representing such data by decomposing the observed data into two factors, where one factor is considered to be the feature and the other the expansion loading from a linear algebra perspective. If the data are sampled from multiple independent subspaces, the loading factor would possess a diagonal structure under an ideal matrix decomposition. However, the standard NMF method and its variants have not been reported to exploit this type of data via direct estimation. To address this issue, a non-negative matrix factorization with multiple constraints model is proposed in this paper. The constraints include an sparsity norm on the feature matrix and a total variational norm on each column of the loading matrix. The proposed model is shown to be capable of efficiently recovering diagonal block structures hidden in observed samples. An efficient numerical algorithm using the alternating direction method of multipliers model is proposed for optimizing the new model. Compared with several benchmark models, the proposed method performs robustly and effectively for simulated and real biological data.

In this study, a new modulation method defined as Ramanujan periodic subspace division multiplexing (RPSDM) is proposed using Ramanujan subspaces. Each subspace contains an integer-valued Ramanujan sum and its circular downshifts as a basis. The proposed RPSDM decomposes the linear time-invariant wireless channels into a Toeplitz stair block diagonal matrices, whereas orthogonal frequency division multiplexing (OFDM) decompose the same into diagonal. Advantages of such structured subspaces representation are studied and compared with an OFDM representation in terms of a peak-average power ratio and bit error rate. Zero-forcing and minimum mean square error detectors are applied to evaluate the performance of OFDM and RPSDM techniques. Finally, the simulation results show that the proposed design (with an additional receiver complexity) outperforms OFDM under both detectors.

Incremental extreme learning machine has been verified that it has the universal approximation capability. However, there are two major issues lowering its efficiency: one is that some “random” hidden nodes are inefficient which decrease the convergence rate and increase the structural complexity, the other is that the final output weight vector is not the minimum norm least-squares solution which decreases the generalization capability. To settle these issues, this paper proposes a simple and efficient algorithm in which the parameters of even hidden nodes are calculated by fitting the residual error vector in the previous phase, and then, all existing output weights are recursively updated based on inverse partitioned matrix. The algorithm can reduce the inefficient hidden nodes and obtain a preferable output weight vector which is always the minimum norm least-squares solution. Theoretical analyses and experimental results show that the proposed algorithm has better performance on convergence rate, generalization capability and structural complexity than other incremental extreme learning machine algorithms.

Spectra from a single intimate (nonlinear) mixture can be modeled as data points drawn from a smooth manifold. Spectral data sets containing hyperspectral observations of multiple intimate mixtures with some constituent materials in common can, therefore, be modeled as data clouds, in which each point is drawn from a union of manifolds that share a boundary. Two important steps in the processing of such data are to: 1) identify the different mixture manifolds present in the data and 2) invert the nonlinear mixing function by mapping each mixture manifold into some low-dimensional Euclidean space (manifold embedding). The present state-of-the-art algorithms for joint manifold clustering and embedding perform poorly for hyperspectral data, particularly in the embedding task. We propose a novel reconstruction-based algorithm for the improved clustering and the embedding of mixture manifolds. The algorithm attempts to reconstruct each target point as an affine combination of its nearest neighbors with an additional rank penalty on the neighborhood to ensure that only the neighbors on the same manifold as the target point are used in the reconstruction. The reconstruction matrix generated by this technique is both block diagonal and neighborhood-based, leading to improved clustering and embedding. The improved performance of the algorithm against its competitors is exhibited on a variety of simulated and real mixture data sets.

A modified hierarchically off-diagonal low-rank (HODLR) fast direct solver is presented to analyze the scattering by electrically large and complex perfect electric conducting objects. The overall idea of HODLR solver is that the impedance matrix can be decomposed into the multiplication of several diagonal block matrices and the inverse is obtained easily with Sherman–Morrison–Woodbury formula. In this paper, a novel modified matrix compression method is utilized for the low-rank approximation of the off-diagonal submatrices. The proposed method only compresses the far-group subblocks judged by extended admissibility condition. The low-rank representations of the off-diagonal submatrices are then reconstructed and recompressed with the help of adaptive tolerance strategy. Consequently, the computation time and storage requirements will reduce significantly compared with the conventional solver. Several numerical results are presented to demonstrate the effectiveness and accuracy of the proposed method.

A new over-identifying restriction test in the generalized method of moments (GMM) estimation of panel data models is proposed. In contrast to the conventional over-identifying restriction test, where the sample covariance matrix of the moment conditions is used in the weighting matrix, the proposed test uses a block diagonal weighting matrix constructed from the efficient optimal weighting matrix. It is shown that the proposed test statistic asymptotically follows the weighted sum of the chi-square distribution with one degree of freedom. A detailed local power analysis is provided for dynamic panel data models, and it is demonstrated that the new test has a comparable power to the conventional J test in many cases. The Monte Carlo simulations reveal that the proposed test has a substantially better size property than the conventional test does.

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson–Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

This paper studies the subspace clustering problem. Given some data points approximately drawn from a union of subspaces, the goal is to group these data points into their underlying subspaces. Many subspace clustering methods have been proposed and among which sparse subspace clustering and low-rank representation are two representative ones. Despite the different motivations, we observe that many existing methods own the common block diagonal property, which possibly leads to correct clustering, yet with their proofs given case by case. In this work, we consider a general formulation and provide a unified theoretical guarantee of the block diagonal property. The block diagonal property of many existing methods falls into our special case. Second, we observe that many existing methods approximate the block diagonal representation matrix by using different structure priors, e.g., sparsity and low-rankness, which are indirect. We propose the first block diagonal matrix induced regularizer for directly pursuing the block diagonal matrix. With this regularizer, we solve the subspace clustering problem by Block Diagonal Representation (BDR), which uses the block diagonal structure prior. The BDR model is nonconvex and we propose an alternating minimization solver and prove its convergence. Experiments on real datasets demonstrate the effectiveness of BDR.

Our work addresses an improvement in accuracy for dimensionality reduction and reconstruction of random signals. The proposed transform targets noisy signals. This is because in the case of highly noisy signals, the known optimal methods might produce a large associated error. Let x, y and u be a source signal with m components, observed noisy signal with n components and reduced signal with k components, respectively, and let c = k / min { m , n } be a reduction ratio (RR) where k ≤ min {m, n}. If RR is fixed then the error associated with the known methods cannot be improved. The purpose of this paper is the development of an approach which leads to the better performance than that of the well-known fundamental techniques. The associated accuracy is improved by an optimal choice of an “auxiliary” random signal v (called the injection) and its dimensionality q, and by the increase in the number of matrices to optimize compared to the known transforms. At the same time, the total number of entries of the matrices is less than for the known related transforms. The proposed method contains, in particular, a special operation Q which transforms the large covariance matrix to the block diagonal form with smaller blocks. The above circumstances make the proposed technique numerically faster than the known related transforms. Numerical examples are provided that illustrate the above advantages.

Self-representation model has made good progress for a single view subspace clustering. This paper proposed the multi-view subspace clustering model based on self-representation. This model assumes that the samples from different classes are embedded in independent subspaces. Thus, the fused multi-view self-representation feature should be block diagonal, and a block diagonal regularizer with the complementarity of multi-view information is given. The model optimization algorithm by alternating minimization is proposed and its convergence without any additional assumption is proved. With the complementarity of multi-view information and the block diagonal property, our model will depict data more comprehensively than single view independently. The extensive experiments on public datasets demonstrate the effectiveness of our proposed model.

Natural images often have self-similarity, which can be used to remove noise. Therefore, many current denoising methods denoise by processing similar image block matrix. Aiming at the problem that these methods will destroy the two-dimensional structure of image blocks when they are expanded into one-dimensional column vectors, a new image denoising method based on high-order singular value decomposition is proposed. Several similar image blocks are stacked into three-dimensional arrays and treated as a third-order tensor; then, higher-order singular value decomposition can be performed. For the core tensor obtained by decomposition, an iterative algorithm with adaptive hard threshold coefficient shrinkage is proposed. The experimental results show that the proposed method outperforms the state-of-the-art methods in peak-signal-to-noise ratio, structural similarity, and visual effects.