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

Sensor selection is a useful method to help reduce computational, hardware, and power requirements while maintaining acceptable performance. Although minimizing the Cramér-Rao bound has been adopted previously for sparse sensing, it did not consider multiple targets and unknown target directions. We propose to tackle the sensor selection problem for direction of arrival estimation using the worst-case Cramér-Rao bound of two uncorrelated equal power sources on planar arrays. We cast the problem as a convex semi-definite program and retrieve the binary selection by randomized rounding. We illustrate the proposed method through numerical examples related to planar arrays. We show that our method selects a combination of edge and center elements, which contrasts with solutions obtained by minimizing the single-target Cramér-Rao bound.@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

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

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

Doppler velocity estimation in pulse-Doppler radar is done by evaluating the target returns of bursts of pulses. While this provides convenience and accuracy, it requires multiple pulses. In adaptive and cognitive radar systems, the ability to adapt on consecutive pulses, instead of bursts, brings potential performance benefits. Hence, with radar transceiver arrays growing increasingly larger in their number of elements over the years, it may be time to re-evaluate how Doppler velocity can be estimated when using large planar arrays. In this work, we present variance bounds on the estimation of velocity using the Doppler shift as it appears in the array model. We also propose an efficient method of performing the velocity estimation and we verify its performance using Monte Carlo simulations.

@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

Graph sampling strategies require the signal to be relatively sparse in an alternative domain, e.g. bandlimitedness for reconstructing the signal. When such a condition is violated or its approximation demands a large bandwidth, the reconstruction often comes with unsatisfactory results even with large samples. In this paper, we propose an alternative sampling strategy based on a type of overcomplete graph-based dictionary. The dictionary is built from graph filters and has demonstrated excellent sparse representations for graph signals. We recognize the proposed sampling problem as a coupling between support recovery of sparse signals and node selection. Thus, to approach the problem we propose a sampling procedure that alternates between these two. The former estimates the sparse support via orthogonal matching pursuit (OMP), which in turn enables the latter to build the sampling set selection through greedy algorithms. Numerical results corroborate the role of key parameters and the effectiveness of the proposed method.@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

Topology identification is an important problem across many disciplines, since it reveals pairwise interactions among entities and can be used to interpret graph data. In many scenarios, however, this (unknown) topology is time-varying, rendering the problem even harder. In this paper, we focus on a time-varying version of the structural equation modeling (SEM) framework, which is an umbrella of multivariate techniques widely adopted in econometrics, epidemiology and psychology. In particular, we view the linear SEM as a first-order diffusion of a signal over a graph whose topology changes over time. Our goal is to learn such time-varying topology from streaming data. To attain this goal, we propose a real-time algorithm, further accelerated by building on recent advances in time-varying optimization, which updates the time-varying solution as a new sample comes into the system. We augment the implementation steps with theoretical guarantees, and we show performances on synthetic and real datasets.@en

A critical task in graph signal processing is to estimate the true signal from noisy observations over a subset of nodes, also known as the reconstruction problem. In this paper, we propose a node-adaptive regularization for graph signal reconstruction, which surmounts the conventional Tikhonov regularization, giving rise to more degrees of freedom; hence, an improved performance. We formulate the node-adaptive graph signal denoising problem, study its bias-variance trade-off, and identify conditions under which a lower mean squared error and variance can be obtained with respect to Tikhonov regularization. Compared with existing approaches, the node-adaptive regularization enjoys more general priors on the local signal variation, which can be obtained by optimally designing the regularization weights based on Prony's method or semidefinite programming. As these approaches require additional prior knowledge, we also propose a minimax (worst-case) strategy to address instances where this extra information is unavailable. Numerical experiments with synthetic and real data corroborate the proposed regularization strategy for graph signal denoising and interpolation, and show its improved performance compared with competing alternatives.@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

Signal processing and machine learning algorithms for data sup-ported over graphs, require the knowledge of the graph topology. Unless this information is given by the physics of the problem (e.g., water supply networks, power grids), the topology has to be learned from data. Topology identification is a challenging task, as the problem is often ill-posed, and becomes even harder when the graph structure is time-varying. In this paper, we address the problem of dynamic topology identification by building on recent results from time-varying optimization, devising a general-purpose online algorithm operating in non-stationary environments. Because of its iteration-constrained nature, the proposed approach exhibits an intrinsic temporal-regularization of the graph topology without explicitly enforcing it. As a case-study, we specialize our method to the Gaussian graphical model (GGM) problem and corroborate its performance.@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

The design of feasible trajectories to traverse the k-space for sampling in magnetic resonance imaging (MRI) is important while considering ways to reduce the scan time. Over the recent years, non-Cartesian trajectories have been observed to result in benign artifacts and being less sensitive to motion. In this paper, we propose a generalized framework that encompasses projection-based methods to generate feasible non-Cartesian k-space trajectories. This framework allows to construct feasible trajectories from both random or structured initial trajectories, e.g., based on the traveling salesman problem (TSP). We evaluate the performance of the proposed methods by simulating the reconstruction of 128 × 128 and 256 × 256 phantom and brain MRI images in terms of structural similarity (SSIM) index and peak signal-to-noise ratio (PSNR) using compressed sensing techniques. It is observed that the TSP-based trajectories from the proposed projection method with constant acceleration parameterization (CAP) result in better reconstruction compared to the projection method with constant velocity parameterization (CVP) and this for a similar read-out time. Further, random-like trajectories are observed to be better than TSP-based trajectories as they reduce the read-out time while providing better reconstruction quality. A reduction in read-out time by upto 67% is achieved using the proposed projection with permutation (PP) method.@en

We consider the scenario of finding the transfer function of an aberrating layer in front of an ultrasound array. We are interested in blindly estimating this transfer function without prior knowledge of the unknown ultrasound sources or ultrasound contrast image. The algorithm gives an exact solution if the matrix representing the aberration layer’s transfer function is full rank, up to a scaling and reordering of its columns, which has to be resolved using some prior knowledge of the matrix structure. We provide conditions for the robustness of blind calibration in noise. Numerical simulations show that the method becomes more robust for shorter wavelengths, as the transfer function matrices then tend to be less ill-conditioned. Image reconstruction from simulated data using the k-Wave toolbox show that a well calibrated model removes some of the distortions introduced by an uncalibrated model, and improves the resolution for some of the sources.@en

In this paper, we revisit the problem of minimizing a convex function f(x) with Lipschitz continuous gradient via accelerated gradient methods (AGM). To do so, we consider the so-called estimate sequence (ES), a useful analysis tool for establishing the convergence of AGM. We develop a generalized ES to support Lipschitz continuous gradient on any norm, given the importance of considering non-Euclidian norms in optimization. Traditionally, ES consists of a sequence of quadratic functions that serves as surrogate functions of f(x). However, such quadratic functions preclude the possibility of supporting Lipschitz continuous gradient defined w.r.t. non-Euclidian norms. Hence, an extension of such a powerful tool to the non-Euclidian norm setting is so much needed. Such extension is accomplished through a simple yet nontrivial modification of the standard ES. Further, our analysis provides insights of how acceleration is achieved and interpretability of the involved parameters in ES. Finally, numerical tests demonstrate the convergence benefits of taking non-Euclidean norms into account.@en

Data defined over a network have been successfully modelled by means of graph filters. However, although in many scenarios the connectivity of the network is known, e.g., smart grids, social networks, etc., the lack of well-defined interaction weights hinders the ability to model the observed networked data using graph filters. Therefore, in this paper, we focus on the joint identification of coefficients and graph weights defining the graph filter that best models the observed input/output network data. While these two problems have been mostly addressed separately, we here propose an iterative method that exploits the knowledge of the support of the graph for the joint identification of graph filter coefficients and edge weights. We further show that our iterative scheme guarantees a non-increasing cost at every iteration, ensuring a globally-convergent behavior. Numerical experiments confirm the applicability of our proposed approach.@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