Systolic finite field multiplier over <inline-formula> <tex-math notation="LaTeX">GF(2^{m}) </tex-math></inline-formula>, because of its superior features such as high throughput and regularity, is ...highly desirable for many demanding cryptosystems. On the other side, however, obtaining high-performance systolic multiplier with relatively low hardware cost is still a challenging task due to the fact that the systolic structure usually involves large area complexity. Based on this consideration, in this paper, we propose to carry out two novel coherent interdependent efforts. First, a new digit-serial multiplication algorithm based on polynomial basis over binary field <inline-formula> <tex-math notation="LaTeX">(GF(2^{m})) </tex-math></inline-formula> is proposed. Novel Toeplitz matrix-vector product (TMVP)-based decomposition strategy is employed to derive an efficient subquadratic space complexity. Second, The proposed algorithm is then innovatively mapped into a low-complexity systolic multiplier, which involves less area-time complexities than the existing ones. A series of resource optimization techniques also has been applied on the multiplier which optimizes further the proposed design (it is the first report on digit-serial systolic multiplier based on TMVP approach covering all irreducible polynomials, to the best of our knowledge). The following complexity analysis and comparison confirm the efficiency of the proposed multiplier, that is, it has lower area-delay product (ADP) than the existing ones. The extension of the proposed multiplier for bit-parallel implementation is also considered in this paper.
Coprime arrays can achieve an increased number of degrees of freedom by deriving the equivalent signals of a virtual array. However, most existing methods fail to utilize all information received by ...the coprime array due to the non-uniformity of the derived virtual array, resulting in an inevitable estimation performance loss. To address this issue, we propose a novel virtual array interpolation-based algorithm for coprime array direction-of-arrival (DOA) estimation in this paper. The idea of array interpolation is employed to construct a virtual uniform linear array such that all virtual sensors in the non-uniform virtual array can be utilized, based on which the atomic norm of the second-order virtual array signals is defined. By investigating the properties of virtual domain atomic norm, it is proved that the covariance matrix of the interpolated virtual array is related to the virtual measurements under the Hermitian positive semi-definite Toeplitz condition. Accordingly, an atomic norm minimization problem with respect to the equivalent virtual measurement vector is formulated to reconstruct the interpolated virtual array covariance matrix in a gridless manner, where the reconstructed covariance matrix enables off-grid DOA estimation. Simulation results demonstrate the performance advantages of the proposed DOA estimation algorithm for coprime arrays.
The β maps Schiavoni-Piazza, Alec J. A.; Meadon, David; Serra, Stefano
Linear algebra and its applications,
2024, Volume:
697
Journal Article
Peer reviewed
Open access
In the current work, we study the eigenvalue distribution results of a class of non-normal matrix-sequences which may be viewed as a low rank perturbation, depending on a parameter beta > 1, of ...the basic Toeplitz matrix-sequence {T-n(e(i theta))}n is an element of N, i(2) = -1. The latter of which has obviously all eigenvalues equal to zero for any matrix order n, while for the matrix-sequence under consideration we will show a strong clustering on the complex unit circle. A detailed discussion on the outliers is also provided. The problem appears mathematically innocent, but it is indeed quite challenging since all the classical machinery for deducing the eigenvalue clustering does not cover the considered case. In the derivations, we resort to a trick used for the spectral analysis of the Google matrix plus several tools from complex analysis. We only mention that the problem is not an academic curiosity and in fact stems from problems in dynamical systems and number theory. Additionally, we also provide numerical experiments in high precision, a distribution analysis in the Weyl sense concerning both eigenvalues and singular values is given, and more results are sketched for the limit case of beta = 1. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).
Starting from measured data, we develop a method to compute the fine structure of the spectrum of the Koopman operator with rigorous convergence guarantees. The method is based on the observation ...that, in the measure-preserving ergodic setting, the moments of the spectral measure associated to a given observable are computable from a single trajectory of this observable. Having finitely many moments available, we use the classical Christoffel–Darboux kernel to separate the atomic and absolutely continuous parts of the spectrum, supported by convergence guarantees as the number of moments tends to infinity. In addition, we propose a technique to detect the singular continuous part of the spectrum as well as two methods to approximate the spectral measure with guaranteed convergence in the weak topology, irrespective of whether the singular continuous part is present or not. The proposed method is simple to implement and readily applicable to large-scale systems since the computational complexity is dominated by inverting an N×N Hermitian positive-definite Toeplitz matrix, where N is the number of moments, for which efficient and numerically stable algorithms exist; in particular, the complexity of the approach is independent of the dimension of the underlying state-space. We also show how to compute, from measured data, the spectral projection on a given segment of the unit circle, allowing us to obtain a finite approximation of the operator that explicitly takes into account the point and continuous parts of the spectrum. Finally, we describe a relationship between the proposed method and the so-called Hankel Dynamic Mode Decomposition, providing new insights into the behavior of the eigenvalues of the Hankel DMD operator. A number of numerical examples illustrate the approach, including a study of the spectrum of the lid-driven two-dimensional cavity flow.
In this paper we consider pentadiagonal (n+1)×(n+1) matrices with two sub-diagonals above and below the main diagonal at distances k and ℓ from the main diagonal where 1≤k<ℓ≤n. We give explicit ...formulae for the eigenpairs of imperfect Toeplitz matrices in the case when (n+1)/2≤k. Imperfectness means that the first and last k elements of the main diagonal differ from the elements in the middle.
A quasi-Toeplitz matrix is a semi-infinite matrix of the form A=T(a)+E, where T(a) is a Toeplitz matrix with entries (T(a))i,j=aj−i, for aj−i∈C, i,j≥1 and E is a compact correction. Quasi-Toeplitz ...M-matrices are encountered in the study of quadratic matrix equations arising in the analysis of a 2-dimensional Quasi-Birth-Death (QBD) stochastic process. We investigate properties of such matrices and provide conditions under which a quasi-Toeplitz matrix is an M-matrix. We show that under a mild and easy-to-check condition, an invertible quasi-Toeplitz M-matrix has a unique square root that is an M-matrix possessing quasi-Toeplitz structure. The quasi-Toeplitz structure of the square root of M-matrices provides inspirations for proving spectral properties of the quadratic matrix polynomial L(λ)=λ2A1+λA0+A−1 having quasi-Toeplitz coefficients where A1,A−1≥0 and −A0 in addition is an M-matrix. Some issues concerning the computation of square root of quasi-Toeplitz M-matrices are discussed and numerical experiments are performed.
In this letter, we address the problem of direction finding using coprime array, which is one of the most preferred sparse array configurations. Motivated by the fact that non-uniform element spacing ...hinders full utilization of the underlying information in the receive signals, we propose a direction-of-arrival (DoA) estimation algorithm based on low-rank reconstruction of the Toeplitz covariance matrix. The atomic-norm representation of the measurements from the interpolated virtual array is considered, and the equivalent dual-variable rank minimization problem is formulated and solved using a cyclic optimization approach. The recovered covariance matrix enables the application of conventional subspace-based spectral estimation algorithms, such as MUSIC, to achieve enhanced DoA estimation performance. The estimation performance of the proposed approach, in terms of the degrees-of-freedom and spatial resolution, is examined. We also show the superiority of the proposed method over the competitive approaches in the root-mean-square error sense.
PDF
