We study the problem of selecting a subset of vectors from a large set to obtain the best signal representation over a family of functions. Although greedy methods have been widely used to tackle this problem and many of those have been analyzed under the lens of (weak) submodularity, none of these algorithms are explicitly devised using such a functional property. Here, we revisit the vector-selection problem and introduce a function that is shown to be submodular in expectation. This function not only guarantees near-optimality through a greedy algorithm in expectation but also alleviates the existing deficiencies in commonly used matching pursuit (MP) algorithms. We further show the relation between the single-point-estimate version of the proposed greedy algorithm and MP variants. Moreover, we discuss extending the signal representation problem to instances with knapsack and matroid constraints. Our theoretical findings are supported by numerical experiments on the angle of arrival estimation problem, a typical signal representation task, demonstrating the benefits of our method compared to traditional MP algorithms.

@en

We consider the scenario of finding the transfer function of an aberrating layer in front of a receiving ultrasound (US) array, assuming a separate non-aberrated transmit source. We propose a method for blindly estimating this transfer function without exact knowledge of the ultrasound sources or acoustic contrast image, and without directly measuring the transfer function using a separate controlled calibration experiment. Instead, the measurement data of many unknown random images is collected, such as from blood flow, and its second-order statistics are exploited. A measurement model is formulated that explicitly defines the layer's transfer function. A covariance domain problem is then defined to eliminate the image variable, and it is solved for the layer's transfer function using manifold-based optimization. The proposed approach and calibration algorithm are evaluated on a range of challenging and realistic simulations using the k-Wave toolbox. Our results show that, given a sufficiently efficient parameterization of the layer's transfer function, and by jointly estimating the transfer function at multiple frequencies, the proposed algorithm is able to obtain an accurate estimate. Subsequent simulated imaging experiments using the obtained transfer function also show increased imaging performance in various aberrating layers, including a skull layer.

@en

One of the main challenges of graph filters is the stability of their design. While classical graph filters allow for a stable design using optimal polynomial approximation theory, generalized graph filters tend to suffer from the ill-conditioning of the involved system matrix. This issue, accentuated for increasing graph filter orders, naturally leads to very large (small) filter coefficients or error saturation, casting a shadow on the benefits of these richer graph filter structures. In addition to this, data-driven design/learning of graph filters with large filter orders, even in the case of classical graph filters, suffers from the eigenvalue spread of the input data covariance matrix and mode coupling, leading to convergence-related issues as the ones observed when identifying time-domain filters with large orders. To alleviate these conditioning and convergence problems, and to reduce the overall design complexity, in this work, we propose a cascaded implementation of generalized graph filters and an efficient algorithm for designing the graph filter coefficients in both model- and data-driven settings. Further, we establish the connections of this implementation with so-called graph convolutional neural networks and demonstrate the performance of the proposed structure in different network applications. By the proposed approach, further error reduction and better design stability are achieved.

@en

This work proposes an algorithmic framework to learn time-varying graphs from online data. The generality offered by the framework renders it model-independent, i.e., it can be theoretically analyzed in its abstract formulation and then instantiated under a variety of model-dependent graph learning problems. This is possible by phrasing (time-varying) graph learning as a composite optimization problem, where different functions regulate different desiderata, e.g., data fidelity, sparsity or smoothness. Instrumental for the findings is recognizing that the dependence of the majority (if not all) data-driven graph learning algorithms on the data is exerted through the empirical covariance matrix, representing a sufficient statistic for the estimation problem. Its user-defined recursive update enables the framework to work in non-stationary environments, while iterative algorithms building on novel time-varying optimization tools explicitly take into account the temporal dynamics, speeding up convergence and implicitly including a temporal-regularization of the solution. We specialize the framework to three well-known graph learning models, namely, the Gaussian graphical model (GGM), the structural equation model (SEM), and the smoothness-based model (SBM), where we also introduce ad-hoc vectorization schemes for structured matrices (symmetric, hollows, etc.) which are crucial to perform correct gradient computations, other than enabling to work in low-dimensional vector spaces and hence easing storage requirements. After discussing the theoretical guarantees of the proposed framework, we corroborate it with extensive numerical tests in synthetic and real data.

@en

To the surprise of most of us, complexity in nature spawns from simplicity. No matter how simple a basic unit is, when many of them work together, the interactions among these units lead to complexity. This complexity is present in the spreading of diseases, where slightly different policies, or conditions,might lead to very different results; or in biological systems where the interactions between elements maintain the delicate balance that keep life running. Fortunately, despite their complexity, current advances in technology have allowed us to have more than just a sneak-peak at these systems. With new views on how to observe such systems and gather data, we aimto understand the complexity within. One of these new views comes from the field of graph signal processing which provides models and tools to understand and process data coming from such complex systems. With a principled view, coming from its signal processing background, graph signal processing establishes the basis for addressing problems involving data defined over interconnected systems by combining knowledge from graph and network theory with signal processing tools. In this thesis, our goal is to advance the current state-of-the-art by studying the processing of network data using graph filters, the workhorse of graph signal processing, and by proposing methods for identifying the topology (interactions) of a network from network measurements. To extend the capabilities of current graph filters, the network-domain counterparts of time-domain filters, we introduce a generalization of graph filters. This new family of filters does not only provide more flexibility in terms of processing networked data distributively but also reduces the communications in typical network applications, such as distributed consensus or beamforming. Furthermore, we theoretically characterize these generalized graph filters and also propose a practical and numerically-amenable cascaded implementation. As allmethods in graph signal processingmake use of the structure of the network, we require to know the topology. Therefore, identifying the network interconnections from networked data is much needed for appropriately processing this data. In this thesis, we pose the network topology identification problem through the lens of system identification and study the effect of collecting information only from part of the elements of the network. We show that by using the state-space formalism, algebraic methods can be applied to the network identification problem successfully. Further, we demonstrate that for the partially-observable case, although ambiguities arise, we can still retrieve a coherent network topology leveraging state-of-the-art optimization techniques.@en

With the well-documented popularity of Frank Wolfe (FW) algorithms in machine learning tasks, the present paper establishes links between FW subproblems and the notion of momentum emerging in accelerated gradient methods (AGMs). On the one hand, these links reveal why momentum is unlikely to be effective for FW-type algorithms on general problems. On the other hand, it is established that momentum accelerates FW on a class of signal processing and machine learning applications. Specifically, it is proved that a momentum variant of FW, here termed accelerated Frank Wolfe (AFW), converges with a faster rate ${\cal O}(\frac{1}{k^2})$ on such a family of problems, despite the same ${\cal O}(\frac{1}{k})$ rate of FW on general cases. Distinct from existing fast convergent FW variants, the faster rates here rely on parameter-free step sizes. Numerical experiments on benchmarked machine learning tasks corroborate the theoretical findings.@en

To deal with high-dimensional data, graph filters have shown their power in both graph signal processing and data science. However, graph filters process signals exploiting only pairwise interactions between the nodes, and they are not able to exploit more complicated topological structures. Graph Volterra models, on the other hand, are also able to exploit relations between triplets, quadruplets and so on. However, they have only been exploited for topology identification and are only based on one-hop relations. In this paper, we first review graph filters and graph Volterra models and then merge the two concepts resulting in so-called topological Volterra filters (TVFs). TVFs process signals over multiple hops of higher-level topological structures. First-level TVFs are basically similar to traditional graph filters, yet higher-level TVFs provide a more general processing framework. We apply TVFs to inverse filtering and recommender systems.@en

Submodularity is a discrete domain functional property that can be interpreted as mimicking the role of well-known convexity/concavity properties in the continuous domain. Submodular functions exhibit strong structure that lead to efficient optimization algorithms with provable near-optimality guarantees. These characteristics, namely, efficiency and provable performance bounds, are of particular interest for signal processing (SP) and machine learning (ML) practitioners, as a variety of discrete optimization problems are encountered in a wide range of applications. Conventionally, two general approaches exist to solve discrete problems: 1) relaxation into the continuous domain to obtain an approximate solution or 2) the development of a tailored algorithm that applies directly in the discrete domain. In both approaches, worst-case performance guarantees are often hard to establish. Furthermore, they are often complex and thus not practical for large-scale problems. In this article, we show how certain scenarios lend themselves to exploiting submodularity for constructing scalable solutions with provable worst-case performance guarantees. We introduce a variety of submodular-friendly applications and elucidate the relation of submodularity to convexity and concavity, which enables efficient optimization. With a mixture of theory and practice, we present different flavors of submodularity accompanying illustrative real-world case studies from modern SP and ML. In all of the cases, optimization algorithms are presented along with hints on how optimality guarantees can be established.

@en

In this article, we explore the state-space formulation of a network process to recover from partial observations the network topology that drives its dynamics. To do so, we employ subspace techniques borrowed from system identification literature and extend them to the network topology identification problem. This approach provides a unified view of network control and signal processing on graphs. In addition, we provide theoretical guarantees for the recovery of the topological structure of a deterministic continuous-time linear dynamical system from input-output observations even when the input and state interaction networks are different. Our mathematical analysis is accompanied by an algorithm for identifying from data,a network topology consistent with the system dynamics and conforms to the prior information about the underlying structure. The proposed algorithm relies on alternating projections and is provably convergent. Numerical results corroborate the theoretical findings and the applicability of the proposed algorithm.

@en

While regularization on graphs has been successful for signal reconstruction, strategies for controlling the bias-variance trade-off of such methods have not been completely explored. In this work, we put forth a node varying regularizer for graph signal reconstruction and develop a minmax approach to design the vector of regularization parameters. The proposed design only requires as prior information an upper bound on the underlying signal energy; a reasonable assumption in practice. With such formulation, an iterative method is introduced to obtain a solution meeting global equilibrium. The approach is numerically efficient and has convergence guarantees. Numerical simulations using real data support the proposed design scheme. @en

In this work, we explore the state-space formulation of network processes to recover the underlying network structure (local connections). To do so, we employ subspace techniques borrowed from system identification literature and extend them to the network topology inference problem. This approach provides a unified view of the traditional network control theory and signal processing on networks. In addition, it provides theoretical guarantees for the recovery of the topological structure of a deterministic linear dynamical system from input-output observations even though the input and state evolution networks can differ. @en

With an increasingly interconnected and digitized world, distributed signal processing and graph signal processing have been proposed to process its big amount of data. However, privacy has become one of the biggest challenges holding back the widespread adoption of these tools for processing sensitive data. As a step towards a solution, we demonstrate the privacypreserving capabilities of variants of the so-called distributed graph filters. Such implementations allow each node to compute a desired linear transformation of the networked data while protecting its own private data. In particular, the proposed approach eliminates the risk of possible privacy abuse by ensuring that the private data is only available to its owner. Moreover, it preserves the distributed implementation and keeps the same communication and computational cost as its non-secure counterparts. Furthermore, we show that this computational model is secure under both passive and eavesdropping adversary models. Finally, its performance is demonstrated by numerical tests and it is shown to be a valid and competitive privacypreserving alternative to traditional distributed optimization techniques. @en

Graph filters are one of the core tools in graph signal processing. A central aspect of them is their direct distributed implementation. However, the filtering performance is often traded with distributed communication and computational savings. To improve this tradeoff, this paper generalizes state-of-the-art distributed graph filters to filters where every node weights the signal of its neighbors with different values while keeping the aggregation operation linear. This new implementation, labeled as edge-variant graph filter, yields a significant reduction in terms of communication rounds while preserving the approximation accuracy. In addition, we characterize a subset of shift-invariant graph filters that can be described with edge-variant recursions. By using a low-dimensional parameterization, these shift-invariant filters provide new insights in approximating linear graph spectral operators through the succession and composition of local operators, i.e., fixed support matrices. A set of numerical results shows the benefits of the edge-variant graph filters over current methods and illustrates their potential to a wider range of applications than graph filtering.

@en

Multiple-input multiple-output (MIMO) radar is known for its superiority over conventional radar due to its antenna and waveform diversity. Although higher angular resolution, improved parameter identifiability, and better target detection are achieved, the hardware costs (due to multiple transmitters and multiple receivers) and high-energy consumption (multiple pulses) limit the usage of MIMO radars in large scale networks. On one hand, higher angle and velocity estimation accuracy is required, but on the other hand, a lower number of antennas/pulses is desirable. To achieve such a compromise, in this paper, the Cramér-Rao lower bound (CRLB) for the angle and velocity estimator is employed as a performance metric to design the antenna and the pulse placement. It is shown that the CRLB derived for two targets is a more appropriate criterion in comparison with the single-target CRLB since the two-target CRLB takes into account both the mainlobe width and the sidelobe level of the ambiguity function. In this paper, several algorithms for antenna and pulse selection based on convex and submodular optimization are proposed. Numerical experiments are provided to illustrate the developed theory.

@en

In this work, we address the problem of identifying the underlying network structure of data. Different from other approaches, which are mainly based on convex relaxations of an integer problem, here we take a distinct route relying on algebraic properties of a matrix representation of the network. By describing what we call possible ambiguities on the network topology, we proceed to employ sub-modular analysis techniques for retrieving the network support, i.e., network edges. To achieve this we only make use of the network modes derived from the data. Numerical examples showcase the effectiveness of the proposed algorithm in recovering the support of sparse networks.

@en

Resolution from co-prime arrays and from a full ULA of the size equal to the virtual size of co-prime arrays is investigated. We take into account not only the resulting beam width but also the fact that fewer measurements are acquired by co-prime arrays. This fact is relevant in compressive acquisition typical for compressive sensing. Our stochastic approach to resolution uses information distances computed from the geometrical structure of data models that is characterized by the Fisher information. The probability of resolution is assessed from a likelihood ratio test by using information distances. Based on this information-geometry approach, we compare stochastic resolution from active co-prime arrays and from the full-size ULA. This novel stochastic resolution analysis is applied in a one-dimensional angle processing. Results demonstrate the suitability in radar-resolution analysis.@en

A bound for sparse reconstruction involving both the signal-to-noise ratio (SNR) and the estimation grid size is presented. The bound is illustrated for the case of a uniform linear array (ULA). By reducing the number of possible sparse vectors present in the feasible set of a constrained ℓ1-norm minimization problem, ambiguities in the reconstruction of a single source under noise can be reduced. This reduction is achieved by means of a proper selection of the estimation grid, which is naturally linked with the mutual coherence of the sensing matrix. Numerical simulations show the performance of sparse reconstruction with an estimation grid meeting the provided bound demonstrating the effectiveness of the proposed bound.@en

In this paper, a new direction of arrival (DOA) estimation approach is devised using concepts from information geometry (IG). The proposed method uses geodesic distances in the statistical manifold of probability distributions parametrized by their covariance matrix to estimate the direction of arrival of several sources. In order to obtain a practical method, the DOA estimation is treated as a single-variable optimization problem, for which the DOA solutions are found by means of a line search. The relation between the proposed method and MVDR beamformer is elucidated. An evaluation of its performance is carried out by means of Monte Carlo simulations and it is shown that the proposed method provides improved resolution capabilities at low SNR with respect to MUSIC and MVDR.@en