Search

This paper presents secrecy analyses of a full-duplex MIMOME network which consists of two full-duplex multi-antenna users (Alice and Bob) and an arbitrarily located multi-antenna eavesdropper (Eve). The paper assumes that Eve's channel state information (CSI) is completely unknown to Alice and Bob except for a small radius of secured zone. The first part of this paper aims to optimize the powers of jamming noises from both users. To handle Eve's CSI being unknown to users, the focus is placed on Eve at the most harmful location, and the large matrix theory is applied to yield a hardened secrecy rate to work on. The performance gain of the power optimization in terms of maximum tolerable number of antennas on Eve is shown to be significant. The second part of this paper shows two analyses of anti-eavesdropping channel estimation (ANECE) that can better handle Eve with any number of antennas. One analysis assumes that Eve has a prior statistical knowledge of its CSI, which yields lower and upper bounds on secure degrees of freedom of the system as functions of the number (N) of antennas on Eve and the size (K) of information packet. The second analysis assumes that Eve does not have any prior knowledge of its CSI but performs blind detection of information, which yields an approximate secrecy rate for the case of K being larger than N. [ABSTRACT FROM AUTHOR]

This paper proposes a momentum algorithm based on Borges difference and an adaptive momentum (Adam) algorithm based on Borges difference to update parameters, which can adjust the momentum information more flexibly. The Borges difference is proposed from the definition of Borges derivative to be combined with the gradient algorithm in convolutional neural networks. The proposed momentum algorithm based on Borges difference and Adam algorithm based on Borges difference can be adjusted more flexibly in order to speed up the convergence. The parameter optimization algorithm with the Borges difference presents a better performance compared with the integer-order momentum algorithm and integer-order Adam algorithm, with the proposed nonlinear adjustment method for the parameter tuning of convolutional neural networks. By analyzing experimental results of Fashion-MNIST dataset and CIFAR-10 dataset, the optimization algorithms based on Borges difference proposed in this paper gain better effects on the optimization model compared with the corresponding ones based on the integer-order difference, and can speed up the convergence speed and recognition accuracy of the image recognition. [ABSTRACT FROM AUTHOR]

Over the decades, multiple approaches have been proposed to solve convex programs. The development of interior-point methods allowed solving a more general set of convex programs known as semi-definite and second-order cone programs. However, these methods are excessively slow for high dimensions. On the other hand, optimization algorithms on manifolds have shown great abilities in finding solutions to non-convex problems in a reasonable time. This paper suggests using a Riemannian optimization approach to solve a subset of convex optimization problems wherein the optimization variable is a doubly stochastic matrix. Optimization over the set of doubly stochastic matrices is crucial for multiple communications and signal processing applications, especially graph-based clustering. The paper introduces and investigates the geometries of three convex manifolds, namely the doubly stochastic, the symmetric, and the definite multinomial manifolds which generalize the simplex, also known as the multinomial manifold. Theoretical complexity analysis and numerical simulation results testify the efficiency of the proposed method over state-of-the-art algorithms. In particular, they reveal that the proposed framework outperforms conventional generic and specialized approaches, especially in high dimensions. [ABSTRACT FROM AUTHOR]

Signal classification problems arise in a wide variety of applications, and their demand is only expected to grow. In this paper, we focus on the wireless sensor network signal classification setting, where each sensor forwards quantized signals to a fusion center to be classified. Our primary goal is to train a decision function and quantizers across the sensors to maximize the classification performance in an online manner. Moreover, we are interested in sparse sensor selection using a marginalized weighted kernel approach to improve network resource efficiency by disabling less reliable sensors with minimal effect on classification performance. To achieve our goals, we develop a multi-sensor online kernel scalar quantization (MSOKSQ) learning strategy that operates on the sensor outputs at the fusion center. Our theoretical analysis reveals how the proposed algorithm affects the quantizers across the sensors. Additionally, we provide a convergence analysis of our online learning approach by studying its relationship to batch learning. We conduct numerical studies under different classification and sensor network settings which demonstrate the accuracy gains from optimizing different components of MSOKSQ and robustness to reduction in the number of sensors selected. [ABSTRACT FROM AUTHOR]

In this paper, we propose new methodologies to decrease the computational cost of safe screening tests for LASSO. We first introduce a new screening strategy, dubbed “joint screening test,” which allows the rejection of a set of atoms by performing one single test. Our approach enables to find good compromises between complexity of implementation and effectiveness of screening. Second, we propose two new methods to decrease the computational cost inherent to the construction of the (so-called) “safe region.” Our numerical experiments show that the proposed procedures lead to significant computational gains as compared to standard methodologies. [ABSTRACT FROM AUTHOR]

Cost-optimization through the minimization of hardware and processing costs with minimal loss in performance is an interesting design paradigm in evolving and emerging Multiple-Input-Multiple-Output (MIMO) radar systems. This optimization is a challenging task due to the increasing Radio Frequency (RF) hardware complexity as well as the signal design algorithm complexity in applications requiring high angular resolution. Towards addressing these, the paper proposes a low-complexity signal design framework, which incorporates a generalized time multiplex scheme for reducing the RF hardware complexity with a subsequent discrete phase modulation. The scheme further aims at achieving simultaneous transmit beamforming and maximum virtual MIMO aperture to enable better target detection and discrimination performance. Furthermore, the paper proposes a low-complexity signal design scheme for beampattern matching in the aforementioned setting. The conducted performance evaluation indicates that the listed design objectives are met. [ABSTRACT FROM AUTHOR]

This paper focuses on optimal time-of-arrival (TOA) sensor placement for multiple target localization simultaneously. In previous work, different solutions only using non-shared sensors to localize multiple targets have been developed. Those methods localize different targets one-by-one or use a large number of mobile sensors with many limitations, such as low effectiveness and high network complexity. In this paper, firstly, a novel optimization model for multi-target localization incorporating shared sensors is formulated. Secondly, the systematic theoretical results of the optimal sensor placement are derived and concluded using the A-optimality criterion, i.e., minimizing the trace of the inverse Fisher information matrix (FIM), based on rigorous geometrical derivations. The reachable optimal trace of Cramér-Rao lower bound (CRLB) is also derived. It can provide optimal conditions for many cases and even closed form solutions for some special cases. Thirdly, a novel numerical optimization algorithm to quickly find and calculate the (sub-)optimal placement and achievable lower bound is explored, when the model becomes complicated with more practical constraints. Then, a hybrid method for solving the most general situation, integrating both the analytical and numerical solutions, is proposed. Finally, the correctness and effectiveness of the proposed theoretical and mathematical methods are demonstrated by several simulation examples. [ABSTRACT FROM AUTHOR]

Compact representation of signals and images is a key for many applications. Compactness is often achieved through linear transforms with good energy concentration property. We present an adaptive wavelet filter bank with fixed number of vanishing moments, plus additional local adaptation. Proposed adaptation method is conducted at each sample according to the least absolute deviation (LAD) criterion. Fixed vanishing moments provide for polynomial annihilation. Adaptation is aimed to achieve maximum sparseness for a wider class of signals, such as sine waves. LAD criterion results in more accurate adaptation on sudden changes of signal statistics. In this paper, an efficient LAD realization is proposed, in spite of nonexistence of the closed form solution. Combining least squares and LAD criterion, we have achieved unbiased adaptation, robust to noise. Due to its simplicity and acceptable computational speed, the proposed scheme is a good candidate for the real-world applications. In this paper, advantages of the proposed scheme are shown in signal denoising and reconstruction. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the secure relay beamforming problems for the amplify-and-forward (AF) relay network, where the transmitter sends the information to the receiver with the help of a multiple-antenna relay in the presence of an eavesdropper. We first study the secrecy rate maximization (SRM) problem in the case of complete channel state information (CSI). The rank-1 relay beamformer, which has been solved in our previous work in “Secure relay beamforming with imperfect channel side information,” IEEE Trans. Veh. Technol., vol. 62, no. 5, pp. 2140–2155, June 2013, is rigorously proved to be globally optimal. Then, we turn to the case of partial eavesdropper’s CSI (ECSI), where the uncertainty of ECSI is characterized as a bounded region, and study the worst-case secrecy rate maximization (WCSRM) problem. Different from the common spherical uncertainty region, the uncertainty region adopted in our paper imposes independent constraints on the channel gain and direction. With the proposed uncertainty region, we give an in-depth analysis of the WCSRM problem. We solve the rank-1 relay beamformer in an explicit form and move a step further by establishing the sufficient conditions for the global optimality of the rank-1 solution. Besides, the rank-2 relay beamformer with a special singular value decomposition (SVD) structure is also considered. By reducing the optimization variables into single variable, we show that the proposed rank-2 solution can be solved by simple line search. The asymptotic optimality of the proposed rank-2 relay beamformer in the high relay power region is also proved under mild conditions. Finally, numerical results are presented to verify the analysis in the paper. [ABSTRACT FROM PUBLISHER]

This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and nonsmooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA (W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” IEEE Trans. Signal Process., vol. 63, no. 22, pp. 6013–6023, 2015), but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Second, for the special case without nonsmooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries. [ABSTRACT FROM AUTHOR]

This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a static networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized constrained quadratic programming and compressed sensing problems, as well as many regularization problems arising in inverse problems, signal processing, and machine learning, which have decentralized applications. This paper addresses the need for efficient decentralized algorithms that take advantages of proximal operations for the nonsmooth terms. We propose a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the composite structure and has the best known convergence rate. It is a nontrivial extension to the recent algorithm EXTRA. At each iteration, each agent locally computes a gradient of the smooth part of its objective and a proximal map of the nonsmooth part, as well as exchanges information with its neighbors. The algorithm is “exact” in the sense that an exact consensus minimizer can be obtained with a fixed step size, whereas most previous methods must use diminishing step sizes. When the smooth part has Lipschitz gradients, PG-EXTRA has an ergodic convergence rate of O\left(1\over k\right) in terms of the first-order optimality residual. When the smooth part vanishes, PG-EXTRA reduces to P-EXTRA, an algorithm without the gradients (so no “G” in the name), which has a slightly improved convergence rate at o\left(1\over k\right) in a standard (non-ergodic) sense. Numerical experiments demonstrate effectiveness of PG-EXTRA and validate our convergence results [ABSTRACT FROM PUBLISHER]

Fractional programming (FP) refers to a family of optimization problems that involve ratio term(s). This two-part paper explores the use of FP in the design and optimization of communication systems. Part I of this paper focuses on FP theory and on solving continuous problems. The main theoretical contribution is a novel quadratic transform technique for tackling the multiple-ratio concave–convex FP problem—in contrast to conventional FP techniques that mostly can only deal with the single-ratio or the max-min-ratio case. Multiple-ratio FP problems are important for the optimization of communication networks, because system-level design often involves multiple signal-to-interference-plus-noise ratio terms. This paper considers the applications of FP to solving continuous problems in communication system design, particularly for power control, beamforming, and energy efficiency maximization. These application cases illustrate that the proposed quadratic transform can greatly facilitate the optimization involving ratios by recasting the original nonconvex problem as a sequence of convex problems. This FP-based problem reformulation gives rise to an efficient iterative optimization algorithm with provable convergence to a stationary point. The paper further demonstrates close connections between the proposed FP approach and other well-known algorithms in the literature, such as the fixed-point iteration and the weighted minimum mean-square-error beamforming. The optimization of discrete problems is discussed in Part II of this paper. [ABSTRACT FROM AUTHOR]

This two-part paper develops novel methodologies for using fractional programming (FP) techniques to design and optimize communication systems. Part I of this paper proposes a new quadratic transform for FP and treats its application for continuous optimization problems. In this Part II of the paper, we study discrete problems, such as those involving user scheduling, which are considerably more difficult to solve. Unlike the continuous problems, discrete or mixed discrete-continuous problems normally cannot be recast as convex problems. In contrast to the common heuristic of relaxing the discrete variables, this work reformulates the original problem in an FP form amenable to distributed combinatorial optimization. The paper illustrates this methodology by tackling the important and challenging problem of uplink coordinated multicell user scheduling in wireless cellular systems. Uplink scheduling is more challenging than downlink scheduling, because uplink user scheduling decisions significantly affect the interference pattern in nearby cells. Furthermore, the discrete scheduling variable needs to be optimized jointly with continuous variables such as transmit power levels and beamformers. The main idea of the proposed FP approach is to decouple the interaction among the interfering links, thereby permitting a distributed and joint optimization of the discrete and continuous variables with provable convergence. The paper shows that the well-known weighted minimum mean-square-error (WMMSE) algorithm can also be derived from a particular use of FP; but our proposed FP-based method significantly outperforms WMMSE when discrete user scheduling variables are involved, both in term of run-time efficiency and optimizing results. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of analog–digital transmit beamforming under spectrum sharing constraints for backhaul systems. In contrast to fully digital designs, where the spatial processing is done at baseband unit with all the flexible computational resources of digital processors, analog–digital beamforming schemes require that certain processing is done through analog components, such as phase-shifters or switches. These analog components do not have the same processing flexibility as the digital processor, but on the other hand, they can substantially reduce the cost and complexity of the beamforming solution. This paper presents the joint optimization of the analog and digital parts, which results in a nonconvex, NP-hard, and coupled problem. In order to solve it, an alternating optimization with a penalized convex–concave method is proposed. According to the simulation results, this novel iterative procedure is able to find a solution that behaves close to the fully digital beamforming upper bound scheme. [ABSTRACT FROM AUTHOR]

Ultra high-throughput satellite systems are expected to play an essential role in future beyond 5G and 6G networks. These systems must remain as flexible as possible to adapt to heterogeneous traffic demands, while also delivering the highest possible rate for dedicated services. Satellites flexible payloads are increasingly employing wideband output multiplexers. In this context, it is now more important than ever to evaluate frequency-dependent degradations on multicarrier signals. In particular, it is critical to characterize the distortions entailed by the output multiplexers filters. In this paper, models are presented and novel formulas are derived to determine the carrier-to-interference ratio resulting from these distortions. Derivations are oriented towards the applicability of either high-accuracy (e.g., for link budget) or low-complexity calculations (e.g., for real-time carrier allocation). The influence of key parameters such as the optimal decision instant, symbol rate and roll-off factor is thoroughly analyzed. Furthermore, formulas are evaluated in a practical scenario: the dynamic carrier allocation optimization. They are combined with efficient optimization algorithms to obtain the best performance based on user fairness. Relevant metrics such as accuracy, complexity and allocation gain are also investigated. In the end, the application of the proposed formulas and algorithms leads to a significant allocation gain that is increasing with the number of carriers. The feasibility of real-time dynamic carrier allocation to further increase the capacity of the next generation of satellite systems is emphasized. [ABSTRACT FROM AUTHOR]

In this paper, we propose multi-input multi-output (MIMO) beamforming designs towards joint radar sensing and multi-user communications. We employ the Cramér-Rao bound (CRB) as a performance metric of target estimation, under both point and extended target scenarios. We then propose minimizing the CRB of radar sensing while guaranteeing a pre-defined level of signal-to-interference-plus-noise ratio (SINR) for each communication user. For the single-user scenario, we derive a closed form for the optimal solution for both cases of point and extended targets. For the multi-user scenario, we show that both problems can be relaxed into semidefinite programming by using the semidefinite relaxation approach, and prove that the global optimum can be generally obtained. Finally, we demonstrate numerically that the globally optimal solutions are reachable via the proposed methods, which provide significant gains in target estimation performance over state-of-the-art benchmarks. [ABSTRACT FROM AUTHOR]

This paper investigates a novel intelligent reflecting surface (IRS)-based symbiotic radio (SR) system architecture consisting of a transmitter, an IRS, and an information receiver (IR). The primary transmitter communicates with the IR and at the same time assists the IRS in forwarding information to the IR. Based on the IRS’s symbol period, we distinguish two scenarios, namely, commensal SR (CSR) and parasitic SR (PSR), where two different techniques for decoding the IRS signals at the IR are employed. We formulate bit error rate (BER) minimization problems for both scenarios by jointly optimizing the active beamformer at the base station and the phase shifts at the IRS, subject to a minimum primary rate requirement. Specifically, for the CSR scenario, a penalty-based algorithm is proposed to obtain a high-quality solution, where semi-closed-form solutions for the active beamformer and the IRS phase shifts are derived based on Lagrange duality and Majorization-Minimization methods, respectively. For the PSR scenario, we apply a bisection search-based method, successive convex approximation, and difference of convex programming to develop a computationally efficient algorithm, which converges to a locally optimal solution. Simulation results demonstrate the effectiveness of the proposed algorithms and show that the proposed SR techniques are able to achieve a lower BER than benchmark schemes. [ABSTRACT FROM AUTHOR]

Distributed primal-dual methods have been widely used for solving large-scale constrained optimization problems. The majority of existing results focus on the problems with decoupled constraints. Some recent works have studied the problems subject to separable globally coupled constraints. This paper considers the distributed optimization problems with globally coupled constraints over networks without requiring the separability of the globally coupled constraints. This is made possible by the local estimates of the constraint violations. For solving such a problem, we propose a primal-dual algorithm in the augmented Lagrangian framework, combining the average consensus technique. We first establish a non-ergodic convergence rate of $\mathcal {O}(1/k)$ in terms of the objective residual for solving a distributed constrained convex optimization problem, where $k$ is the iteration counter. Specifically, the global objective function is the aggregate of the local convex and possibly non-smooth costs, and the coupled constraint is the sum of the local linear equality constraints. The numerical results illustrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

This paper studies the convergence properties of the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate. [ABSTRACT FROM AUTHOR]

Principal component analysis (PCA) is a classical and ubiquitous method for reducing data dimensionality, but it is suboptimal for heterogeneous data that are increasingly common in modern applications. PCA treats all samples uniformly so degrades when the noise is heteroscedastic across samples, as occurs, e.g., when samples come from sources of heterogeneous quality. This paper develops a probabilistic PCA variant that estimates and accounts for this heterogeneity by incorporating it in the statistical model. Unlike in the homoscedastic setting, the resulting nonconvex optimization problem is not seemingly solved by singular value decomposition. This paper develops a heteroscedastic probabilistic PCA technique (HePPCAT) that uses efficient alternating maximization algorithms to jointly estimate both the underlying factors and the unknown noise variances. Simulation experiments illustrate the comparative speed of the algorithms, the benefit of accounting for heteroscedasticity, and the seemingly favorable optimization landscape of this problem. Real data experiments on environmental air quality data show that HePPCAT can give a better PCA estimate than techniques that do not account for heteroscedasticity. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the $\ell _1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms with provable guarantees for tackling this problem. Specifically, our contribution is fourfold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a global sublinear rate. Furthermore, we show that ManPPA can achieve a local quadratic convergence rate when applied to sharp instances of the problem. Second, we develop a semismooth Newton-based inexact augmented Lagrangian method for computing the search direction in each iteration of ManPPA and show that it has an asymptotic superlinear convergence rate. Third, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Fourth, using ManPPA as a building block, we propose a new heuristic method for solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods. [ABSTRACT FROM AUTHOR]

Stochastic compositional optimization generalizes classic (non-compositional) stochastic optimization to the minimization of compositions of functions. Each composition may introduce an additional expectation. The series of expectations may be nested. Stochastic compositional optimization is gaining popularity in applications such as reinforcement learning and meta learning. This paper presents a new Stochastically Corrected Stochastic Compositional gradient method (SCSC). SCSC runs in a single-time scale with a single loop, uses a fixed batch size, and guarantees to converge at the same rate as the stochastic gradient descent (SGD) method for non-compositional stochastic optimization. This is achieved by making a careful improvement to a popular stochastic compositional gradient method. It is easy to apply SGD-improvement techniques to accelerate SCSC. This helps SCSC achieve state-of-the-art performance for stochastic compositional optimization. In particular, we apply Adam to SCSC, and the exhibited rate of convergence matches that of the original Adam on non-compositional stochastic optimization. We test SCSC using the model-agnostic meta-learning tasks. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering a group sparse vector from a small number of linear measurements. In the past, the common approach has been to use various “group sparsity-inducing” norms such as the Group LASSO norm for this purpose. By using the theory of convex relaxations, we show that it is also possible to use $\ell _1$ -norm minimization for group sparse recovery. We introduce a new concept called group robust null space property (GRNSP), and show that, under suitable conditions, a group version of the restricted isometry property (GRIP) implies the GRNSP, and thus leads to group sparse recovery. When all groups are of equal size, our bounds are sometimes less conservative than known bounds. Moreover, our results apply even to situations where the groups have different sizes. When specialized to conventional sparsity, our bounds reduce to one of the well-known “best possible” conditions for sparse recovery. This relationship between GRNSP and GRIP is new even for conventional sparsity, and substantially streamlines the proofs of some known results. Using this relationship, we derive bounds on the $\ell _p$ -norm of the residual error vector for all $p \in [1,2]$ , and not just when $p = 2$. When the measurement matrix consists of random samples of a sub-Gaussian random variable, we present bounds on the number of measurements, which are sometimes less conservative than currently known bounds. [ABSTRACT FROM AUTHOR]

Regularized zero-forcing beamforming (RZFB) is an interesting class of linear signal processing problems, which is very attractive for use in large-scale communication networks due its simple visualization as a straightforward extension of the well-accepted zero-forcing beamforming (ZFB). However, unlike ZFB, which is multi-user interference free, RZFB must manage multi-user interference to achieve its high throughput performance. Most existing works focus on the performance analysis of particular RZBF schemes such as the equip-power allocated RZBF under a fixed regularization parameter. This paper is the first work to consider the joint design of power allocation and regularization parameter for RZFB to maximize the worst users’ throughput or the quality-of-service awarded energy efficiency under a fixed transmit power constraint. Such designs pose very computationally challenging optimization problems, for which the paper proposes two-stage optimization algorithms of low computational complexity. Their computational and performance efficiencies are substantiated through numerical examples. [ABSTRACT FROM AUTHOR]

This paper studies linear distributed estimation of an unknown random parameter vector in a bandwidth-constrained multisensor network. To meet the bandwidth limitations, each sensor converts its observation into a low-dimensional datum via a suitable linear transformation. Then, the fusion center estimates the parameter vector by linearly combining all the received low-dimensional data, aiming at minimizing the estimation mean square error. The main purpose of this paper is to jointly determine the compression dimension of each sensor (referred to as dimension assignment) and design the corresponding compression matrix when the total compression dimensions is limited. Such a joint design problem can be formulated as a rank-constrained optimization problem and it is shown to be NP-hard for the first time. In addition, successive quadratic upper-bound minimization (SQUM), SQUM-block coordinate descent (SQUM-BCD) and nuclear norm regularization (NNR) methods are developed to solve it approximately. Furthermore, we show that any accumulation point of the sequence generated by the SQUM method satisfies the Karush-Kuhn-Tucker conditions of the rank-constrained optimization problem, and the Phase II algorithm of the SQUM-BCD and NNR methods (both are two-phase algorithms and have the same Phase II algorithm) guarantees convergence at least to a stationary point. Numerical experiments illustrate the advantages of the proposed methods compared with the existing method. [ABSTRACT FROM AUTHOR]

Numerical optimization has played a central role in addressing key signal processing (SP) problems. Highly effective methods have been developed for a large variety of SP applications such as communications, radar, filter design, and speech and image analytics, just to name a few. However, optimization algorithms often entail considerable complexity, which creates a serious gap between theoretical design/analysis and real-time processing. In this paper, we aim at providing a new learning-based perspective to address this challenging issue. The key idea is to treat the input and output of an SP algorithm as an unknown nonlinear mapping and use a deep neural network (DNN) to approximate it. If the nonlinear mapping can be learned accurately by a DNN of moderate size, then SP tasks can be performed effectively—since passing the input through a DNN only requires a small number of simple operations. In our paper, we first identify a class of optimization algorithms that can be accurately approximated by a fully connected DNN. Second, to demonstrate the effectiveness of the proposed approach, we apply it to approximate a popular interference management algorithm, namely, the WMMSE algorithm. Extensive experiments using both synthetically generated wireless channel data and real DSL channel data have been conducted. It is shown that, in practice, only a small network is sufficient to obtain high approximation accuracy, and DNNs can achieve orders of magnitude speedup in computational time compared to the state-of-the-art interference management algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimizing the expected value of a (possibly nonconvex) cost function parameterized by a random (vector) variable, when the expectation cannot be computed accurately (e.g., because the statistics of the random variables are unknown and/or the computational complexity is prohibitive). Classical stochastic gradient methods for solving this problem may suffer from slow convergence. In this paper, we propose a stochastic parallel Successive Convex Approximation-based (best-response) algorithm for general nonconvex stochastic sum-utility optimization problems, which arise naturally in the design of multi-agent networks. The proposed novel decomposition approach enables all users to update their optimization variables in parallel by solving a sequence of strongly convex subproblems, one for each user. Almost sure convergence to stationary points is proved. We then customize the algorithmic framework to solve the stochastic sum rate maximization problem over single-input-single-output (SISO) frequency-selective interference channels, multiple-input-multiple-output (MIMO) interference channels, and MIMO multiple-access channels. Numerical results corroborate that the proposed algorithms can converge faster than state-of-the-art stochastic gradient schemes while achieving the same (or better) sum-rates. [ABSTRACT FROM AUTHOR]

This paper considers linear downlink transceiver design for the sum power minimization problem with per-user rate constraints in a multi-cell multi-user MIMO system. This non-convex problem is divided into transmit and receive beamforming optimization steps which are iteratively repeated such that the sum power converges. The transmit beamformers are solved using a successive convex approximation method (SCA), whereas the receive beamformers are computed via the linear minimum mean square error (MMSE) criterion. In addition to centralized design, we propose two decentralized algorithms where the transmit and receive beamforming designs are facilitated by a combination of pilot and backhaul signaling. In the first algorithm, sum power is minimized by computing the transmit beamformers at each base station (BS) and the receive beamformers at each user via iterative over-the-air optimization process. BS side processing requires local effective channel state information (CSI) acquired from precoded uplink pilots. In the second algorithm, the transmit and receive beamformers are iteratively optimized at each BS requiring only local CSI obtained from antenna-specific uplink pilots. In both algorithms, transmit beamforming optimization is decoupled among the BSs via primal decomposition method, which requires scalar backhaul information exchange for decentralized processing. The performance of the proposed algorithms is evaluated via numerical examples under different system settings in static and time-correlated channel conditions. [ABSTRACT FROM AUTHOR]

Impulsive processes frequently occur in many fields, such as radar, sonar, communications, audio and speech processing, and biomedical engineering. In this paper, we propose a nonconvex linear regression (NLR) based minimum dispersion beamforming technique for impulsive signals to achieve significant performance improvement over the conventional minimum variance beamformer. The proposed beamformer minimizes the \ellp-norm of the output with p<1 subject to a linear distortionless response constraint, resulting in a difficult nonconvex and nonsmooth optimization problem. The constrained optimization problem is first reduced to a multivariate linear regression via constraint elimination. As a major contribution of this paper, a coordinate descent algorithm (CDA) is devised for solving the resultant NLR problem of \ellp-minimization with p<1 at a computational complexity of \cal O(MN^2), where M is the number of sensors and N is the sample size. At each inner iteration of the CDA, an efficient algorithm is designed to find the global minimum of each subproblem of univariate linear regression. The convergence of the CDA is analyzed. The NLR beamformer with a single constraint is further generalized to the case of multiple linear constraints, which is robust against model mismatch. Simulation results demonstrate the superior performance of nonconvex optimization based beamformer. [ABSTRACT FROM AUTHOR]

Classification with a sparsity constraint on the solution plays a central role in many high dimensional signal processing applications. In some cases, the features can be grouped together, so that entire subsets of features can be selected or discarded. In many applications, however, this can be too restrictive. In this paper, we are interested in a less restrictive form of structured sparse feature selection: We assume that while features can be grouped according to some notion of similarity, not all features in a group need be selected for the task at hand. The Sparse Group Lasso (SGL) was proposed to solve problems of this form. The main contributions of this paper are a new procedure called Sparse Overlapping Group (SOG) lasso, an extension to the SGL to overlapping groups and theoretical sample complexity bounds for the same. We establish model selection error bounds that specializes to many other cases. We experimentally validate our proposed method on both real and toy datasets. [ABSTRACT FROM AUTHOR]

The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments. [ABSTRACT FROM AUTHOR]

Networked radar systems have been demonstrated to offer enhanced target tracking capabilities. An effective radar resource allocation strategy can efficiently optimize system parameters, leading to performance enhancements. In this paper, two critical but limited system resources are considered for optimization: the number of radar nodes and the transmitted power. In this scenario, a joint node selection and power allocation (JSPA) strategy is developed with the objective of tracking multiple targets. The proposed mechanism implements the optimal resource allocation based on the feedback information in the tracking recursion cycle in order to improve the worst-case tracking accuracy with multiple targets. The network architecture considered in this paper is decentralized so that communication requirements may be reduced while maintaining system robustness. Since the predicted conditional Cramér–Rao lower bound (PC-CRLB) provides a lower bound on the accuracy of the target state estimates conditional on the actual measurement realizations, it is more accurate than the standard posterior CRLB and is thus derived and used as an optimization criterion for the JSPA strategy. It is shown that the optimal JSPA is a two-variable nonconvex optimization problem. We propose an efficient two-step semidefinite programming based solution to solve this problem. Numerical results demonstrate the superior performance of the proposed strategy and the effectiveness of the proposed solution. [ABSTRACT FROM AUTHOR]

Even though sparse recovery (SR) has been successfully applied in a wide range of research communities, there still exists a barrier to real applications because of the inefficiency of the state-of-the-art algorithms. In this paper, we propose a dynamical approach to SR, which is highly efficient and with finite-time convergence property. First, instead of solving the $\ell _1$ regularized optimization programs that requires exhausting iterations, which is computer-oriented, the solution to SR problem in this paper is resolved through the evolution of a continuous dynamical system which can be realized by analog circuits. Moreover, the proposed dynamical system is proved to have the finite-time convergence property, and thus more efficient than locally competitive algorithm (LCA) (the recently developed dynamical system to solve SR) with exponential convergence property. Consequently, our proposed dynamical system is more appropriate than LCA to deal with the time-varying situations. Simulations are carried out to demonstrate the superior properties of our proposed system. [ABSTRACT FROM PUBLISHER]

Existing work regarding the performance comparison between nonorthogonal multiple access (NOMA) and orthogonal multiple access (OMA) can be generally divided into two categories. The work in the first category aims to develop analytical results for the comparison, often with fixed system parameters. The work in the second category aims to propose efficient algorithms for optimizing these parameters, and compares NOMA with OMA by computer simulations. However, when these parameters are optimized, the theoretical superiority of NOMA over OMA is still not clear. Therefore, in this paper, the theoretical performance comparison between NOMA and conventional OMA systems is investigated, from an optimization point of view. First, sum rate maximizing problems considering user fairness in both NOMA and various OMA systems are formulated. Then, by using the method of power splitting, a closed-form expression for the optimum sum rate of NOMA systems is derived. Moreover, the fact that NOMA can always outperform any conventional OMA systems, when both are equipped with the optimum resource allocation policies, is validated with rigorous mathematical proofs. Finally, computer simulations are conducted to validate the correctness of the analytical results. [ABSTRACT FROM PUBLISHER]

Superdirective arrays have been extensively studied because of their considerable potential accompanied, unfortunately, by a high sensitivity to random errors that affect the responses and positions of array elements. However, the statistics of their actual beam pattern (BP) has never been systematically investigated. This paper shows that the Rician probability density function (PDF), sometimes adopted to study the impact of errors in conventional arrays, is a valid approximation for superdirective BP statistics only where some mathematical terms are negligible. The paper also shows that this is the case for all linear end-fire arrays considered. A similar study is proposed concerning the correlation between BP lobes, showing that for the superdirective arrays considered the lobes, especially non-adjacent ones, are almost independent. Furthermore, knowledge of the PDF of the actual BP allows one to define quantile BP functions, whose probability of being exceeded, at any point, is fixed. Combining the lobes’ independence with quantile BP functions, an empirical equation for the probability that the entire actual BP will not exceed a quantile function over an interval larger than a given size is obtained. This new knowledge and these tools make it possible to devise new methods to design robust superdirective arrays via optimization goals with clearer and more relevant statistical meaning. [ABSTRACT FROM AUTHOR]

This paper considers the integrated waveform design to simultaneously achieve a desired radar beampattern and multi-users communication for a dual-function Multiple-Input Multiple-Output (MIMO) system. To this end, a spatio-spectral modulation strategy via shaping the spatial waveform Energy Spectral Density (ESD) in directions of communication is proposed for the communication function, while beampattern Integrated Sidelobe Level (ISL) is minimized to enhance radar detectability. Meanwhile, Peak-to-Average Ratio (PAR) and power restrictions to comply with the current hardware technique and the mainlobe width constraint to cohere the beampattern main energy on the spatial region of interest are forced, respectively. Exploiting an equivalent reformulation of the original non-convex optimization problem, a Sequential Block Enhancement (SBE) framework that alternately updates each waveform in each emitting antenna is developed to monotonically decrease ISL. Each block involves the Dinkelbach’s procedure, sequential convex approximation and Alternating Direction Method of Multipliers (ADMM) to obtain single waveform, while the analytic proof with the converged block being a Karush-Kuhn-Tucker (KKT) point is provided. Finally, numerical results highlight the effectiveness of both the proposed dual function scheme and the waveform synthesis technique in comparison with some counterparts. [ABSTRACT FROM AUTHOR]

This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before; however, they suffer from slow convergence rates. This work, equipped with momentum based gradient tracking technique, guarantees fast convergence rates on par with the best-known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. We further propose the novel trimmed FW variants that enjoy the same convergence rates as their classical counterparts, but are empirically shown to require significantly fewer calls to the linear minimization oracle speeding up the overall algorithm. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem. [ABSTRACT FROM AUTHOR]

Many signal processing and machine learning problems can be formulated as consensus optimization problems which can be solved efficiently via a cooperative multi-agent system. However, the agents in the system can be unreliable due to a variety of reasons: noise, faults and attacks. Providing erroneous updates leads the optimization process in a wrong direction, and degrades the performance of distributed machine learning algorithms. This paper considers the problem of decentralized learning using ADMM in the presence of unreliable agents. First, we rigorously analyze the effect of erroneous updates (in ADMM learning iterations) on the convergence behavior of the multi-agent system. We show that the algorithm linearly converges to a neighborhood of the optimal solution under certain conditions and characterize the neighborhood size analytically. Next, we provide guidelines for network design to achieve a faster convergence to the neighborhood. We also provide conditions on the erroneous updates for exact convergence to the optimal solution. Finally, to mitigate the influence of unreliable agents, we propose ROAD, a robust variant of ADMM, and show its resilience to unreliable agents with an exact convergence to the optimum. [ABSTRACT FROM AUTHOR]

Hammerstein model with a static nonlinearity followed by a linear filter is commonly used in numerous applications. This paper focuses on adaptive filtering techniques for parameter identification of Hammerstein systems and output prediction of nonlinear systems. By formulating the underlying filtering problem as a recursive bilinear least-squares optimization with the non-convex feasible region constraint, we develop a recursive non-convex projected least-squares (RncPLS) algorithm based on alternating direction method of multipliers (ADMM). The RncPLS algorithm alternates between implementing ridge regression and projecting on the non-convex feasible set, which successively refines the system parameters. The convergence and accuracy properties of the proposed RncPLS algorithm are theoretically investigated. Moreover, extensive simulation results in the context of system identification, nonlinear predication, and acoustic echo cancellation, are also included to demonstrate the performance characteristics of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, sparsification techniques aided online prediction algorithms in a reproducing kernel Hilbert space are studied for nonstationary time series. The online prediction algorithms as usual consist of the selection of kernel structure parameters and the kernel weight vector updating. For structure parameters, the kernel dictionary is selected by sparsification techniques with selective online modeling criteria, and the symmetric kernel covariance matrix is intermittently optimized with the covariance matrix adaptation evolution strategy (CMA-ES). This intermittent optimization can not only improve the kernel structure’s flexibility by utilizing the cross relatedness of input variables, but also partly alleviate the prediction uncertainty arisen by the kernel dictionary selection for nonstationary time series. In order to sufficiently capture the underlying dynamic characteristics in prediction-error time series, a generalized optimization strategy is designed to sequentially construct the kernel dictionary selection and weight vector updating procedures in multiple kernel connection modes. The generalized optimization strategy is highly flexible and effective, and it is capable of enhancing the ability to adaptively track the changing dynamic characteristics due to nonstationarity. Finally, in the perspective of top-level design, we summarize the information interaction between the network topology in kernel regressors and the optimization of inner model parameters. Numerical simulations demonstrate that the proposed approach has superior prediction performance for nonstationary time series. [ABSTRACT FROM AUTHOR]

Due to the growth of modern dataset size and the desire to harness computing power of multiple machines, there is a recent surge of interest in the design of distributed machine learning algorithms. However, distributed algorithms are sensitive to Byzantine attackers who can send falsified data to prevent the convergence of algorithms or lead the algorithms to converge to value of the attackers’ choice. Some recent work proposed interesting algorithms that can deal with the scenario when up to half of the workers are compromised. In this paper, we propose a novel algorithm that can deal with an arbitrary number of Byzantine attackers. The main idea is to ask the parameter server to randomly select a small clean dataset and compute noisy gradient using this small dataset. This noisy gradient will then be used as a ground truth to filter out information sent by compromised workers. We show that the proposed algorithm converges to the neighborhood of the population minimizer regardless the number of Byzantine attackers. We further provide numerical examples to show that the proposed algorithm can benefit from the presence of good workers and achieve better performance than existing algorithms. [ABSTRACT FROM AUTHOR]

Level-set optimization formulations with data-driven constraints minimize a regularization functional subject to matching observations to a given error level. These formulations are widely used, particularly for matrix completion and sparsity promotion in data interpolation and denoising. The misfit level is typically measured in the $\ell _2$ norm, or other smooth metrics. In this paper, we present a new flexible algorithmic framework that targets nonsmooth level-set constraints, including $\ell _1$ , $\ell _\infty$ , and even $\ell _0$ norms. These constraints give greater flexibility for modeling deviations in observation and denoising, and have significant impact on the solution. Measuring error in the $\ell _1$ and $\ell _0$ norms makes the result more robust to large outliers, while matching many observations exactly. We demonstrate the approach for basis pursuit denoise (BPDN) problems as well as for extensions of BPDN to matrix factorization, with applications to interpolation and denoising of 4D seismic data. The new methods are particularly promising for seismic applications, where the amplitude in the data varies significantly, and measurement noise in low-amplitude regions can wreak havoc for standard Gaussian error models. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new Bayesian model to solve the Robust PCA problem - recovering the underlying low-rank matrix and sparse matrix from their noisy compositions. We first derive and analyze a new objective function, which is proven to be equivalent to the fundamental objective of minimizing the “rank+sparsity”. To solve this objective, we develop a concise Sparse Bayesian Learning (SBL) method that makes minimal assumptions and effectively deals with the requirements of the problem. The concise modeling allows simple and effective Empirical Bayesian inference via maximum a posteriori expectation-maximization (MAP-EM). We further propose a modified SBL method that additionally utilizes the sparsity pattern information of the outliers in the Robust PCA problem. Simulation studies demonstrate the superiority of the proposed methods over the existing state-of-the-art methods. The efficacy of the proposed methods is further verified through two image processing tasks. [ABSTRACT FROM AUTHOR]

In Part II of this two-part paper, we develop novel numerical optimization approaches to design omnidirectional precoding schemes for a massive multiple-input multiple-output system equipped with a uniform rectangular array (URA). To this end, we first formulate the omnidirectional precoding design as a semidefinite program (SDP) with rank constraint. An iterative rank-reduction algorithm is then proposed to produce omnidirectional transmission solution with a minimum number of precoding vectors. It is shown that the proposed algorithm can always obtain three precoding vectors (i.e., a rank-3 precoding matrix) to generate a perfectly omnidirectional power radiation pattern for any $P \times Q$ URA with $\min \lbrace P, Q\rbrace >2$ , or yield an omnidirectional transmission solution with (theoretically minimum) two precoding vectors for any $P \times Q$ URA with $\min \lbrace P, Q\rbrace \leq 2$. In addition, to facilitate analog precoding design, we further impose constant-modulus constraints for every entries of the precoding matrix. Through judicious (re-)formulation, we develop an efficient Newton's method, which can compute four constant-modulus precoding vectors to generate an omnidirectional power radiation pattern for any URA configuration. The numerical results demonstrate the merits of the proposed schemes. [ABSTRACT FROM AUTHOR]

In this paper, we consider the two-timescale queue-aware resource control for wireless video streaming applications. By applying a singular perturbation approach, we study a two-timescale joint optimization of transmission power and streaming rate control for real-time video streaming. The timescale parameter $\epsilon$ is introduced to separate the state variables into slow and fast varying groups, and the power control is adaptive to both the channel state information and the playback queue state information (QSI) at the fast timescale, while the streaming rate representing the video quality is only adaptive to the QSI at the slow timescale. We first derive the averaged system by taking the perturbation parameter $\epsilon \rightarrow 0$ , and the limiting problem is a firm approximation for the formal problem with small $\epsilon$. Based on the averaged system, we derive the Hamilton–Jacobi–Bellman equation and show that the optimal control policy has a structural property which can further help us to simplify the problem. We use the parametric policy reinforcement learning algorithm to obtain the optimal parameterized policy, and show the algorithm convergence result. Finally, the proposed scheme's performance is compared with various baselines through simulations and it is shown that significant gain can be achieved. [ABSTRACT FROM AUTHOR]

With the help of auxiliary data, tensor completion may better recover a low rank multidimensional array from limited observation entries. Most existing methods, including coupled matrix-tensor factorization and coupled tensor rank minimization, mainly focus on how to extract and incorporate subspace or directly use auxiliary data for tensor completion. They are either sensitive to a given rank or lack of physical interpretations of subspace information. In addition, the shared subspace information receives little attention in current tensor completion methods, especially there is no analysis of its impact on sample complexity. In this paper, we propose to separately explore and exploit shared subspaces for tensor completion. Specifically, dictionary learning takes the subspace from auxiliary data in the first step. Then a low rank optimization model for tensor completion is provided to incorporate the trained subspace by assuming that the recovered tensor is composed of two low rank components where one shares the subspace information with auxiliary data and the other is outside the shared space. Based on this optimization model, we make a quantitative analysis to illustrate the effect of subspace information on sample complexity, and provide theoretical insights into the usefulness of subspace information. Finally, experiments on simulated data are conducted to validate the theoretical analysis on the impact of subspace information. Experiments in two real-world applications including color image and multispectral image recovery show that the proposed method outperforms state-of-the-art ones in terms of prediction accuracy and CPU time. [ABSTRACT FROM AUTHOR]

In this paper, we propose two communication-efficient decentralized optimization algorithms over a general directed multi-agent network. The first algorithm, termed Compressed Push-Pull (CPP), combines the gradient tracking Push-Pull method with communication compression. We show that CPP is applicable to a general class of unbiased compression operators and achieves linear convergence rate for strongly convex and smooth objective functions. The second algorithm is a broadcast-like version of CPP (B-CPP), and it also achieves linear convergence rate under the same conditions on the objective functions. B-CPP can be applied in an asynchronous broadcast setting and further reduce communication costs compared to CPP. Numerical experiments complement the theoretical analysis and confirm the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, wepropose a novel two-stage transmission framework for an intelligent reflecting surface (IRS) assisted millimeter wave (mmWave) system in the presence of phase error caused by hardware impairments. Specifically, in Stage I, we introduce a pilot-based phase calibration task and reformulate it as an alternating optimization program. Building on this formulation, an efficient iterative algorithm is developed to jointly estimate the phase error, which needs to be calibrated, and the channels corresponding to the first user. Stage II consists of two blocks, channel estimation and data transmission. During the channel estimation block, by leveraging on the sparsity of mmWave channels, we propose a fast Fourier transform based scheme to estimate the IRS-BS channel and user-IRS channels. During the data transmission block, based on the estimated channel state information, base station precoders and IRS phase shifts are jointly optimized to maximize the sum signal-to-leakage-plus-noise ratio of all users. To handle this non-convex problem, we further develop a low-complexity joint beamforming algorithm by exploiting fractional programming techniques. Moreover, to examine the performance of the proposed phase calibration scheme, we derive the Cramer-Rao lower bound for the intended phase error estimation. Simulation results validate the effectiveness of our proposed transmission framework and the necessity of IRS phase calibration. [ABSTRACT FROM AUTHOR]

Data representation techniques have made a substantial contribution to advancing data processing and machine learning (ML). Improving predictive power was the focus of previous representation techniques, which unfortunately perform rather poorly on the interpretability in terms of extracting underlying insights of the data. Recently, the Kolmogorov model (KM) was studied, which is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. The existing KM learning algorithms using semi-definite relaxation with randomization (SDRwR) or discrete monotonic optimization (DMO) have, however, limited utility to big data applications because they do not scale well computationally.In this paper, we propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. To make our method more scalable to large-dimensional problems, we propose two acceleration schemes, namely, the eigenvalue decomposition (EVD) elimination strategy and an approximate EVD algorithm. Furthermore, a thresholding technique by exploiting the error bound analysis and leveraging the normalized Minkowski $\ell _1$ -norm, is provided for the selection of the number of iterations of the approximate EVD algorithm. When applied to big data applications, it is demonstrated that the proposed method can achieve compatible training/prediction performance with significantly reduced computational complexity; roughly two orders of magnitude improvement in terms of the time overhead, compared to the existing KM learning algorithms. Furthermore, it is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds 80%. [ABSTRACT FROM AUTHOR]

This paper seeks to combine linear time-invariant (LTI) filtering and sparsity-based denoising in a principled way in order to effectively filter (denoise) a wider class of signals. LTI filtering is most suitable for signals restricted to a known frequency band, while sparsity-based denoising is suitable for signals admitting a sparse representation with respect to a known transform. However, some signals cannot be accurately categorized as either band-limited or sparse. This paper addresses the problem of filtering noisy data for the particular case where the underlying signal comprises a low-frequency component and a sparse or sparse-derivative component. A convex optimization approach is presented and two algorithms derived: one based on majorization-minimization (MM), and the other based on the alternating direction method of multipliers (ADMM). It is shown that a particular choice of discrete-time filter, namely zero-phase noncausal recursive filters for finite-length data formulated in terms of banded matrices, makes the algorithms effective and computationally efficient. The efficiency stems from the use of fast algorithms for solving banded systems of linear equations. The method is illustrated using data from a physiological-measurement technique (i.e., near infrared spectroscopic time series imaging) that in many cases yields data that is well-approximated as the sum of low-frequency, sparse or sparse-derivative, and noise components. [ABSTRACT FROM PUBLISHER]