The development of graph neural networks has been driven by the widespread area of applications where graphs are naturally fit and by the advances in making solutions scalable. When it comes to spectral graph convolutional networks (GCNs), directed graphs suffer from the asymmetric nature of their Laplacian matrices. For such graphs, there is no natural extension of the spectral graph theory well-established for their undirected analogues with inherent symmetric matrices. In this paper, we propose i-DGCN: a spectral GCN approach addressing directed graphs by means of a novel symmetric Laplacian matrix constructed using a quantification of the interaction between the nodes. In order to assess i-DGCN, we undertake two tasks: anomaly detection for graph-structured data (unsupervised) and graph link existence prediction (supervised). Then, we compare the results with other Laplacian alternatives for directed graphs.

Graphs can model various systems, activities, or interactions. As a consequence, the ability to detect anomalies in graph-structured data is needed in many scenarios. This paper introduces Community-Augmented Local-Link Intensity (CALLI), an algorithm for quantifying the abnormality extent of nodes in a weighted digraph. Experiments are performed on both synthetically generated and real graphs modeling financial transactions. Throughout the tests, CALLI is directly used as the sole decision-making anomaly score, but also as a feature in a conventional outlier detection approach.

We extend the notion of sparse representation to the case where the atoms are not vectors, but cones, hence infinite sets. The sparse representation is linear, as usual, but the most convenient vector is chosen from each selected cone. We give a cone version of Orthogonal Matching Pursuit (OMP) and show that its complexity is only a few times larger than that of OMP. The new cone OMP can be used for anomaly detection; we apply it with very good results to the detection of abnormal heartbeats.

In this paper we present new methods of anomaly detection based on Dictionary Learning (DL) and Kernel Dictionary Learning (KDL). The main contribution consists in the adaption of known DL and KDL algorithms in the form of unsupervised methods, used for outlier detection. We propose a reduced kernel version (RKDL), which is useful for problems with large data sets, due to the large kernel matrix. We also improve the DL and RKDL methods by the use of a random selection of signals, which aims to eliminate the outliers from the training procedure. All our algorithms are introduced in an anomaly detection toolbox and are compared to standard benchmark results.

Pairwise, or separable, dictionaries are suited for the sparse representation of 2D signals in their original form, without vectorization. They are equivalent with enforcing a Kronecker structure on a standard dictionary for 1D signals. We present a dictionary learning algorithm, in the coordinate descent style of Approximate K-SVD, for such dictionaries. The algorithm has the benefit of extremely low complexity, clearly lower than that of existing algorithms. Experimental evidence shows that the performance of the proposed algorithm is comparable to that of standard (unstructured) AK-SVD with the same number of atoms.

Designing frames with low mutual coherence is a challenging problem, with many applications in signal processing. We adopt an atom-by-atom optimization strategy for obtaining frames with a given mutual coherence. The underlying min-max problem is transformed into a weighted least squares problem, approximately solved with the shifted power method. The resulting algorithm is extremely simple, works directly with the frame and consists of almost only matrix-vector multiplications. Numerical experiments shows that it is especially efficient for frames with a large overcompleteness factor and can design in reasonable time frames much larger than those obtained by other existing methods.

The problem of dictionary learning (DL) for sparse representations can be approximately solved by several algorithms. Regularization of the optimization objective (representation error) was proved useful, since it avoids possible bottlenecks due to nearly linearly dependent atoms. We show here how the well-known K-SVD algorithm can be adapted to the regularized DL problem, despite previous claims that such an adaptation seems impossible. We also provide numerical evidence that regularized K-SVD is better than Simultaneous Codeword Optimization, the most prominent algorithm dedicated to the regularized DL problem.

Abstract Terrain data can be processed from the double perspective of computer graphics and graph theory. We propose a hybrid method that uses geometrical and vertex attribute information to construct a weighted graph reflecting the variability of the vertex data. As a planar graph, a generic terrain data set is subjected to a geometry‐sensitive vertex partitioning procedure. Through the use of a combined, thin‐plate energy and multi‐dimensional quadric metric error, feature estimation heuristic, we construct ‘even’ and ‘odd’ node subsets. Using an invertible lifting scheme, adapted from generic weighted graphs, detail vectors are extracted and used to recover or filter the node information. The design of the prediction and update filters improves the root mean squared error of the signal over general graph‐based approaches. As a key property of this design, preserving the mean of the graph signal becomes essential for decreasing the error measure and conserving the salient shape features.

We propose a low complexity method for estimating direction of arrival (DOA) when the positions of the array sensors are affected by errors with known magnitude bound. This robust DOA method is based on solving an optimization problem whose solution is obtained in two stages. First, the problem is relaxed and the corresponding power estimation has an expression similar to that of standard beamforming. If the relaxed solution does not satisfy the magnitude bound, an approximation is made by projection. Unlike other robust DOA methods, no eigenvalue decomposition is necessary and the complexity is similar to that of MVDR. For low and medium SNR, the proposed method competes well with more complex methods and is clearly better than MVDR.

We present a method for optimization with sums of exponentials subject to positivity constraints and apply it to the modeling of empirical probability distribution functions and to the design of IIR filters with non-negative impulse response. Our approach uses exponents in a sparse arithmetic progression and hence is able to transform the positivity condition to a polynomial form that is computationally tractable. We show how to obtain initial values for the exponents by sparsifying a full progression and then present an iterative optimization procedure using gradient steps. The modeling and design examples indicate a good behavior of our method.

In this paper we present an efficient initialization strategy that improves the performance of overcomplete dictionary learning algorithms. The procedure exploits incoherent structures that can be manipulated and adapted to a given dataset relatively fast. The algorithm involves an iterative adaptation of the dictionary to the dataset with pruning of the less used atoms and constructions of new atoms that fit the data better. Experimental simulations show that the proposed method improves the performance of classical and new developments in dictionary learning algorithms.

We present an improved Adaptive Matching Pursuit algorithm for computing approximate sparse solutions for overdetermined systems of equations. The algorithms use a greedy approach, based on a neighbor permutation, to select the ordered support positions followed by a cyclical optimization of the selected coefficients. The sparsity level of the solution is estimated on-line using Information Theoretic Criteria. The performance of the algorithm approaches that of the sparsity informed RLS, while the complexity remains lower than that of competing methods.

The problem of training a dictionary for sparse representations from a given dataset is receiving a lot of attention mainly due to its applications in the fields of coding, classification and pattern recognition. One of the open questions is how to choose the number of atoms in the dictionary: if the dictionary is too small then the representation errors are big and if the dictionary is too big then using it becomes computationally expensive. In this letter, we solve the problem of computing efficient dictionaries of reduced size by a new design method, called Stagewise K-SVD, which is an adaptation of the popular K-SVD algorithm. Since K-SVD performs very well in practice, we use K-SVD steps to gradually build dictionaries that fulfill an imposed error constraint. The conceptual simplicity of the method makes it easy to apply, while the numerical experiments highlight its efficiency for different overcomplete dictionaries.

We present a sliding window RLS for sparse filters, based on the greedy least squares algorithm. The algorithm adapts a partial QR factorization with pivoting, using a simplified search of the filter support that relies on a neighbor permutation technique. For relatively small window size, the proposed algorithm has a lower complexity than recent exponential window RLS algorithms. Time-varying FIR channel identification simulations show that the proposed algorithm can also give better mean squared coefficient errors.

The topic discussed here is the least-squares design of three-dimensional two-channel filter banks with quincunx sampling. The proposed algorithm uses a transformation of variables that reduces the original problem to designing filters with minimum stopband energy. We split the involved optimization into three steps, the first two consisting of convex problems. To prove the capability of our method we compare our results with another approach of the problem.

We propose a two-stage method for designing nonseparable nearly orthogonal 2-D two-channel filter banks. The first stage consists of solving a convex optimization problem, obtained by relaxing the paraunitarity constraint to a bound on the polyphase matrix norm. The solution of the first stage is used as initialization for the second stage standard optimization. The resulting filters have good passband phase linearity and reconstruction error and compare favorably with previous designs.

The problem under study here is the minimax design of linear-phase lowpass FIR filters having variable passband width and implemented through a Farrow structure. We have two main contributions. The first is the design of adjustable FIR filters without discretization, using 2D positive trigonometric polynomials, an approach leading to semidefinite programming (SDP) formulation of the design problem. The second is to modify the design problem by a special choice for the passband and stopband edges of the variable FIR filter. The advantage is a lower implementation complexity. The new problem is solved using positive hybrid real-trigonometric polynomials and their SDP parameterization. Design examples prove the viability of our methods.

We point out that the algorithm for designing two-channel orthogonal filterbanks proposed by Karmarkar is a particular case of a previous algorithm. Also, we correct an error in the cited paper.

In this letter, we expand upon the method of Tay for the design of orthonormal Q-shift filters for the dual-tree complex wavelet transform. The method of Tay searches for good Hilbert-pairs in a one-parameter family of conjugate-quadrature filters that have one vanishing moment less than the Daubechies conjugate-quadrature filters (CQFs). In this letter, we compute feasible sets for one- and two-parameter families of CQFs by employing the trace parameterization of nonnegative trigonometric polynomials and semidefinite programming. This permits the design of CQF pairs that define complex wavelets that are more nearly analytic, yet still have a high number of vanishing moments.

A wide variety of optimization problems involving nonnegative polynomials or trigonometric polynomials can be formulated as convex optimization problems by expressing (or relaxing) the constraints using sum-of-squares representations. The semidefinite programming problems that result from this formulation are often difficult to solve due to the presence of large auxiliary matrix variables. In this paper we extend a recent technique for exploiting structure in semidefinite programs derived from sum-of-squares expressions to multivariate trigonometric polynomials. The technique is based on an equivalent formulation using discrete Fourier transforms and leads to a very substantial reduction in the computational complexity. Numerical results are presented and a comparison is made with general-purpose semidefinite programming algorithms. As an application, we consider a two-dimensional FIR filter design problem.

We propose a method for the minimax design of 2-D FIR filters based on a parameterization of multivariate trigonometric polynomials that are positive on a given frequency domain. The parameterization uses sum-of-squares polynomials and so semidefinite programming (SDP) is applicable. The frequency domain is expressed via the positivity of some trigonometric polynomials. The degree of sum-of-square polynomials must be bounded and so the method is in principle suboptimal, but the 2-D FIR filter designs we study numerically suggest that near-optimal results are obtained

We propose an efficient algorithm for designing the prototype filters of oversampled, near perfect reconstruction (NPR), GDFT modulated, biorthogonal filterbanks with arbitrary delay. Given the analysis prototype, we show that the minimization of the stopband energy of the synthesis prototype, subject to NPR constraints on the frequency response of the distortion transfer function, can be expressed as a convex optimization problem. Our algorithm consists of initialization with the prototype of an orthogonal filterbank and then successive optimization of the synthesis and analysis prototypes. We compare our algorithm with previous methods and give several design examples.

We propose a new form of the bounded real lemma (BRL), dedicated to finite impulse response (FIR) multiple-input-multiple-output systems. The proposed form is more efficient than the usual adaptation of the standard BRL. As an example, we show how to design the FIR inverse of a FIR periodic filter by using a mixed H/sub 2//H/sub /spl infin// criterion.

Simplified procedures for quasi-equiripple infinite-impulse response (IIR) filter design are proposed. The procedures can be applied in designs where the number of poles is low compared to the number of zeros. The design is initialized with an IIR filter optimizing a least squares criterion. In the simplified procedures, namely simplified iterative reweighting and fixed poles least pth design, the poles of the filter are kept fixed in the succeeding iterative optimization of the numerator. The simplified designs are compared to complete iterative reweighting, where complete IIR design is performed at each iteration. The simplified design is much faster with very small departure from optimality.

Regularity constraints may be added in the design of compaction filters in two ways, named by us explicit and implicit. Most of the previous work used the explicit approach. We show that the implicit form is much more appropriate in terms of numerical accuracy. We also integrate the implicit approach in the semidefinite programming (SDP) framework, guaranteeing thus global optimality.

We present a design method for optimal energy compaction IIR filters, where the numerator and denominator may have different degrees. The design is performed via iterative relaxations, where the numerator is optimized given the denominator, followed by optimization of denominator given the numerator. The two optimization problems involved are solved using semidefinite programming (SDP) techniques, where the real positiveness of the causal part of the product filter is formulated in two alternative ways: first using the Kalman-Yakubovich-Popov (KYP) lemma, and second, by a less-known parameterization (Genin et al., 2000; Stoica et al., 2000), which we show to be more convenient numerically. Numerical results show the effectiveness of the proposed method and the improvements when compared with optimal FIR compaction filters or constrained IIR compaction filters (restricted to have allpass polyphase components).

This paper presents an algorithm for designing an FIR paraunitary filter bank when one or several filters are given. The algorithm is based on the properties of the balanced state-space representation of the polyphase matrix. We show that this representation may be computed via a single RQ decomposition thus gaining significant efficiency with respect to previous work. Application of the algorithm to signal-adapted filter banks is also discussed.

We propose a new technique for finding the optimum FIR compaction filter adapted to signal statistics. The main novelty of our approach is the transformation of the original problem into the maximum eigenvalue minimization of a parameterized Toeplitz matrix, with only O(N) variables. This is a typical application of semidefinite programming (SDP) and may be solved with reliable interior-point algorithms. Our algorithm is to be compared with the method of Tuqan and Vaidyanathan (1998), which has O(N/sup 2/) variables. The numerical experiments show that the optimum compaction filter is obtained with good numerical accuracy and convenient execution time for filters of order up to 100.