Search

Multiple signal classification (MUSIC) is a widely used direction of arrival (DoA)/angle of arrival (AoA) estimation algorithm applied to various application domains, such as autonomous driving, medical imaging, and astronomy. However, MUSIC is computationally expensive and challenging to implement in low-power hardware, requiring exploration of tradeoffs between accuracy, cost, and power. We present MUSIC-lite, which exploits approximate computing to generate a design space exploring accuracy-area-power tradeoffs. This is specifically applied to the computationally intensive singular value decomposition (SVD) component of the MUSIC algorithm in an orthogonal frequency-division multiplexing (OFDM) radar use case. MUSIC-lite incorporates approximate adders into the iterative CORDIC algorithm that is used for hardware implementation of MUSIC, generating interesting accuracy-area-power tradeoffs. Our experiments demonstrate MUSIC-lite’s ability to save an average of 17.25% on-chip area and 19.4% power with a minimal 0.14% error for efficient MUSIC implementations. [ABSTRACT FROM AUTHOR]

Social networks are an important part of our community. In this context, certified dominating sets help to find in networks a group of people, referring as officials, such that 1) for each civilian, there is an official that can serve the civilian, and 2) no official is adjacent to exactly one civilian, to prevent potential abuses. To delve deeper into this topic, this study considers two approaches to the problem of finding certified dominating sets of small cardinality. One approach is to transform an ordinary dominating set, which is subject only to condition 1) given above, into a certified dominating set. The second approach involves constructing such a set from scratch. To compare the two methods, we first studied the computational complexity of the decision problem of whether, for a given graph, the domination number, which is the minimum size of a dominating set, is equal to the certified domination number, that is, the minimum size of a certified dominating set. Next, we constructed and compared the performance of two approximate algorithms that find certified dominating sets, one for each of the two approaches. The effectiveness and efficiency of the proposed algorithms were validated through experiments that compare their results with each other and with a previous study: the linear-time algorithm, which determines the certified domination number for trees and with known results for the domination number in social networks.

Meta-heuristic algorithms, especially evolutionary algorithms, have been frequently used to find near optimal solutions to combinatorial optimization problems. The evaluation of such algorithms is often conducted through comparisons with other algorithms on a set of benchmark problems. However, even if one algorithm is the best among all those compared, it still has difficulties in determining the true quality of the solutions found because the true optima are unknown, especially in dynamic environments. It would be desirable to evaluate algorithms not only relatively through comparisons with others, but also in absolute terms by estimating their quality compared to the true global optima. Unfortunately, true global optima are normally unknown or hard to find since the problems being addressed are NP-hard. In this paper, instead of using true global optima, lower bounds are derived to carry out an objective evaluation of the solution quality. In particular, the first approach capable of deriving a lower bound for dynamic capacitated arc routing problem (DCARP) instances is proposed, and two optimization algorithms for DCARP are evaluated based on such a lower bound approach. An effective graph pruning strategy is introduced to reduce the time complexity of our proposed approach. Our experiments demonstrate that our approach provides tight lower bounds for small DCARP instances. Two optimization algorithms are evaluated on a set of DCARP instances through the derived lower bounds in our experimental studies, and the results reveal that the algorithms still have room for improvement for large complex instances. [ABSTRACT FROM AUTHOR]

To address the challenges of efficient hardware design for error-tolerant applications, several techniques of applied approximate computing have been proposed. Pruning algorithms aim to approximate circuits with reduced design requirements at the cost of an acceptable degradation of their quality of result. In this letter, we present the effects of resynthesis, an iterative application of logic synthesis along with pruning algorithms, into a state-of-the-art approximate design flow, AxLS. Resynthesis strategy improves the approximation, achieving up to 70% area-power savings for the same error in the output, and reducing the number of iterations, and hence the time required to explore the design space in up to $30\times $ , to obtain an approximated design. [ABSTRACT FROM AUTHOR]

This research centers on the application of the discrete-time Taylor–Fourier transform (DTTFT) algorithmic implementation for phasor estimation on a field-programmable gate array board. The system employs a finite impulse response structure of a digital Taylor–Fourier filter to extract amplitude and phase information. The hardware description utilizes a multiply accumulator architecture with only forty embedded 9-bit multiplier elements, achieving an 18-bit input–output resolution. Performance assessment involves signal analysis through FPGA-in-the-loop simulation in MATLAB/Simulink. Findings demonstrate that the DTTFT-based phasor estimator can be effectively characterized using VHDL code and implemented on an Intel D2-115 board. [ABSTRACT FROM AUTHOR]

The advancement of intelligent manufacturing has significantly increased the complexity and demand for efficient automated logistics systems in multi-floor manufacturing and warehousing environments. This paper presents a novel integrated queuing network model for automated vehicle storage and retrieval systems (AVS/RS) that allows for rapid performance estimation in multi-level and multi-depth configurations. The model bridges the gap between traditional simulation and analytical approaches, enabling quick evaluations during the design phase. The study conducts numerical experiments and simulation verifications to assess the impact of different rack configurations on system performance. Key findings include the optimal horizontal and vertical design of racks, showing that increasing the number of aisles and sub-tiers can enhance throughput and reduce cycle time. Additionally, it is shown that a lower number of main tiers leads to better performance, even with the same total number of tiers. The results offer valuable insights for designing efficient AVS/RS, contributing to improved flexibility and efficiency in automated logistics systems. This research has practical implications for optimizing storage solutions in complex, multi-floor manufacturing environments, ultimately enhancing operational efficiency.

Multiobjective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multiobjective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multiobjective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multiobjective shortest-path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA)—the go-to approach for tackling optimization problems on near-term quantum computers—we examine the Pareto plot that results from the scheme and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA and identify key challenges associated with this approach. Finally, through Amazon Braket, we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

Approximate computing is an evolving paradigm that aims to improve the power, speed, and area in neural network applications that can tolerate errors up to a specific limit. This letter proposes a new multiplier architecture based on the algorithm that adapts the approximate compressor from the existing and proposed compressors’ set to reduce error in the respective partial product columns. Further, the error due to the approximation in the proposed multiplier is corrected using a simple error-correcting module. Results prove that the power and power–delay product (PDP) of an 8-bit multiplier is improved by up to 39.9% and 43.6% compared with the exact multiplier and 27.5% and 23.9% compared to similar previous designs. The proposed multiplier is validated using image processing and neural network applications to prove its efficacy. [ABSTRACT FROM AUTHOR]

Recently, multi-objective evolutionary algorithms (MOEAs) have shown promising performance in terms of community detection in complex networks. However, most studies have focused on designing different strategies to achieve good community detection performance based on a single population. Unlike these studies, this study proposes a macro-micro population-based co-evolutionary multi-objective algorithm called MMCoMO for community detection in complex networks to obtain a better trade-off between exploration and exploitation. This algorithm employs two populations, i.e., macro-population and micro-population, for co-evolution to obtain better community structures. In particular, the macro-population prefers exploration and is responsible for quickly determining approximate partitions of the network to obtain good rough community structures as early as possible, whereas the micro-population favors exploitation and is responsible for searching for good fine community structures through the local search process. Thus, these two populations can be used to improve each other through interactions in the co-evolutionary process. In particular, a guiding strategy is designed using the elite (non-dominated) solutions of the macro-population to guide the micro-population, and an influencing strategy is further designed using the elite solutions of the micro-population to positively influence the macro-population. Experiments on synthetic networks and 14 real-world networks demonstrate the superiority of the proposed algorithm over several state-of-the-art community detection algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a novel data-driven approach to designing orthonormal transform matrix codebooks for adaptive transform coding of any non-stationary vector processes which can be considered locally stationary. Our algorithm, which belongs to the class of block-coordinate descent algorithms, relies on simple probability models such as Gaussian or Laplacian for transform coefficients to directly minimize with respect to the orthonormal transform matrix the mean square error (MSE) of scalar quantization and entropy coding of transform coefficients. A difficulty commonly encountered in such minimization problems is imposing the orthonormality constraint on the matrix solution. We get around this difficulty by mapping the constrained problem in Euclidean space to an unconstrained problem on the Stiefel manifold and leveraging known algorithms for unconstrained optimization on manifolds. While the basic design algorithm directly applies to non-separable transforms, an extension to separable transforms is also proposed. We present experimental results for adaptive transform coding of still images and video inter-frame prediction residuals, comparing the transforms designed using the proposed method and a number of other content-adaptive transforms recently reported in the literature. [ABSTRACT FROM AUTHOR]

We present an efficient algorithm to approximate the Automatic Color Equalization (ACE) of an input color image, with an upper-bound on the introduced approximation error. The computation is based on Summed Area Tables and a carefully optimized partitioning of the plane into rectangular regions, resulting in a pseudo-linear asymptotic complexity with the number of pixels (against a quadratic straightforward computation of ACE). Our experimental evaluation confirms both the speedups and high accuracy, reaching lower approximation errors than existing approaches. We provide a publicly available reference implementation of our algorithm. [ABSTRACT FROM AUTHOR]

Multi-Codebook Quantization (MCQ) is a generalized version of existing codebook-based quantizations for Approximate Nearest Neighbor (ANN) search. Specifically, MCQ picks one codeword for each sub-codebook independently and takes the sum of picked codewords to approximate the original vector. The objective function involves no constraints, therefore, MCQ theoretically has the potential to achieve the best performance because solutions of other codebook-based quantization methods are all covered by MCQ’s solution space under the same codebook size setting. However, finding the optimal solution to MCQ is proved to be NP-hard due to its encoding process, i.e., converting an input vector to a binary code. To tackle this, researchers apply constraints to it to find near-optimal solutions or employ heuristic algorithms that are still time-consuming for encoding. Different from previous approaches, this paper takes the first attempt to find a deep solution to MCQ. The encoding network is designed to be as simple as possible, so the very complex encoding problem becomes simply a feed-forward. Compared with other methods on three datasets, our method shows state-of-the-art performance. Notably, our method is $11\times $ - $38\times $ faster than heuristic algorithms for encoding, which makes it more practical for the real scenery of large-scale retrieval. Our code is publicly available: https://github.com/DeepMCQ/DeepQ. [ABSTRACT FROM AUTHOR]

Digital images often suffer from the common problem of stripe noise due to the inconsistent bias of each column. The existence of the stripe poses much more difficulties on image denoising since it requires another ${n}$ parameters, where ${n}$ is the width of the image, to characterize the total interference of the observed image. This paper proposes a novel EM-based framework for simultaneous stripe estimation and image denoising. The great benefit of the proposed framework is that it splits the overall destriping and denoising problem into two independent sub-problems, i.e., calculating the conditional expectation of the true image given the observation and the estimated stripe from the last round of iteration, and estimating the column means of the residual image, such that a Maximum Likelihood Estimation (MLE) is guaranteed and it does not require any explicit parametric modeling of image priors. The calculation of the conditional expectation is the key, here we choose a modified Non-Local Means algorithm to calculate the conditional expectation because it has been proven to be a consistent estimator under some conditions. Besides, if we relax the consistency requirement, the conditional expectation could be interpreted as a general image denoiser. Therefore other state-of-the-art image denoising algorithms have the potentials to be incorporated into the proposed framework. Extensive experiments have demonstrated the superior performance of the proposed algorithm and provide some promising results that motivate future research on the EM-based destriping and denoising framework. [ABSTRACT FROM AUTHOR]

Fleet sizing is an important problem in the planning procedure of one-way car-sharing systems. This article investigates the fleet-sizing problem for reservation-based car-sharing systems allowing cruise parking. The system with traffic congestion is modeled as a mixed queuing network with its servers mapping the remaining road capacity. The optimal fleet size with maximum operating profit is derived, taking into account asymptotic performance metrics like reservation, vehicle availability and utilization, and occupancy of parking spaces of each of the stations. The solution is obtained based on an exact mean value analysis (MVA) algorithm and an approximate Schweitzer–Bard MVA (SB-MVA) algorithm. Numerical experiments demonstrate that the proposed method with cruise parking can meet the travel demands with greatly reduced operating cost. Another interesting finding is that a larger reservation time window implies lower parking capacity and smaller fleet size, whereas, as the time window exceeds a threshold, reducing the fleet size may damage the quality of service. [ABSTRACT FROM AUTHOR]

The ECOsystem Spaceborne Thermal Radiometer Experiment on Space Station (ECOSTRESS) onboard the International Space Station (ISS) provides standard land surface temperature (LST) products to meet community concerns on water stress and evapotranspiration. In 2019, an anomaly on the mass storage unit (MSU) changed the data acquisition mode of ECOSTRESS to a direct streaming one, eliminating three bands centered at 1.60, 8.29, and $9.20~\mu \text{m}$. This letter analyzes the feasibility of retrieving LST from ECOSTRESS data using split-window (SW) techniques which need only two thermal infrared (TIR) bands to serve as an alternative to produce LST products. Three different spilt-window algorithms have been developed and analyzed for all possible TIR band combinations using the simulated top-of-atmosphere (TOA) radiance dataset. Besides, the selected SW algorithms were validated using the intercomparison method with ECOSTRESS LST product data and the temperature-based method with surface radiation budget (SURFRAD) ground-based measurements. The result showed that SW algorithms provided higher accuracies than the temperature-emissivity separation (TES) algorithm, with the main advantage that the atmospheric profile data is not demanded prior. [ABSTRACT FROM AUTHOR]

The missile-borne synthetic aperture radar (SAR) works in the forward-squint state, and a higher flight speed will cause a very large relative radial velocity between the target and the antenna phase center (APC). The classic polar format algorithm (PFA) and its improved version do not effectively compensate for the intra-pulse Doppler history resulting from large radial velocity, which leads to defocused images. Therefore this letter proposes a modified version of the PFA, which can solve such image defocus. Compared with the classical PFA, the modified PFA has the same advantages of simplicity and efficiency while implementing higher image quality by compensation of the residual phases caused by large radial velocity. The modified PFA is suitable for hardware implementation, since only fast Fourier transform (FFT) and complex vector multiplications are required in the range dimension processing. In this letter, simulation examples are employed to verify the validity and advantages of the modified PFA. [ABSTRACT FROM AUTHOR]

In this letter, a high-resolution synthetic aperture radar (SAR) imaging algorithm based on a modified omega-K algorithm is proposed. The proposed algorithm first multiplies the reference signal. Then, the azimuth nonstationary phase error (ANSPE) is considered after performing the interpolation process based on the generalized frequency scale transformation. Finally, a well-focused SAR image can be obtained after compensating the ANSPE and correcting the residual spatial variant range migration by utilizing the range segmentation technique. The simulation results of point targets and the real-measured airborne high-resolution SAR data simultaneously verify the effectiveness and feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Two-dimensional phase unwrapping (PU) is an essential step in interferometric synthetic aperture radar (InSAR) analysis. Although the $L^{0}$ -norm PU method is desired, it is nondeterministic polynomial (NP)-hard. Thus, many PU methods have been proposed to find near-optimal solutions of the $L^{0}$ -norm. As PU is an ill-posed problem, it is difficult to choose the method with the most accurate solution unless reference data are available. In this letter, we prove that the NP-hardness of the $L^{0}$ -norm is weak, suggesting that the $\alpha $ -approximation algorithm of the $L^{0}$ -norm can be devised, that is, the obtained near-optimal solutions can be within a factor of $\alpha $ of the $L^{0}$ -norm optimal value. The primary contribution of the proof is that the $\alpha $ value of each obtained PU solution can be considered as a new index to assess the PU performance without using reference data. The validity and effectiveness of the $\alpha $ -based index have been verified using simulated and acquired interferometric datasets and three PU methods. [ABSTRACT FROM AUTHOR]

This article proposes a lateral vehicle trajectory planning and control algorithm using a model predictive control (MPC) scheme for an automated perpendicular parking system. Previous work showed that approximated clothoid-based local path planning using a virtual towing distance provides low computational time and the stability of lateral vehicle motion in a parking system. However, this approach cannot function in certain parking situations and may cause undesirable steering maneuvers due to state-dependent planning. We present a new approximated clothoid path based on lateral vehicle kinematics to cope with these problems. Using the proposed kinematic model, we formulate an MPC problem for path planning. Then, the proposed lateral vehicle trajectory planning becomes an MPC problem under constraints. Besides, we show that lateral vehicle motion for vertical parking can be implemented using simple kinematic lateral motion control. Experimental results show that the vehicle with the proposed method moves smoothly and completes the given parking mission under constraints, even under tight parking space conditions. [ABSTRACT FROM AUTHOR]

Least-mean-squares (LMS) solvers such as Linear / Ridge-Regression and SVD not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as matrix factorizations. We suggest an algorithm that gets a finite set of $n$ n $d$ d -dimensional real vectors and returns a subset of $d+1$ d + 1 vectors with positive weights whose weighted sum is exactly the same. The constructive proof in Caratheodory's Theorem computes such a subset in $O(n^2d^2)$ O (n 2 d 2) time and thus not used in practice. Our algorithm computes this subset in $O(nd+d^4\log {n})$ O (n d + d 4 log n) time, using $O(\log n)$ O (log n) calls to Caratheodory's construction on small but “smart” subsets. This is based on a novel paradigm of fusion between different data summarization techniques, known as sketches and coresets. For large values of $d$ d , we suggest a faster construction that takes $O(nd)$ O (n d) time and returns a weighted subset of $O(d)$ O (d) sparsified input points. Here, a sparsified point means that some of its entries were set to zero. As an application, we show how to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed data is trivial. Extensive experimental results and open source code are provided. [ABSTRACT FROM AUTHOR]

How can we efficiently find very large numbers of clusters C in very large datasets N of potentially high dimensionality D? Here we address the question by using a novel variational approach to optimize Gaussian mixture models (GMMs) with diagonal covariance matrices. The variational method approximates expectation maximization (EM) by applying truncated posteriors as variational distributions and partial E-steps in combination with coresets. Run time complexity to optimize the clustering objective then reduces from O(NCD) per conventional EM iteration to O(N′G2D) for a variational EM iteration on coresets (with coreset size N ′ ≤ N and truncation parameter G ≪ C). Based on the strongly reduced run time complexity per iteration, which scales sublinearly with NC, we then provide a concrete, practically applicable, parallelized and highly efficient clustering algorithm. In numerical experiments on standard large-scale benchmarks we (A) show that also overall clustering times scale sublinearly with NC, and (B) observe substantial wall-clock speedups compared to already highly efficient recently reported results. The algorithm’s sublinear scaling allows for applications at scales where alternative methods cease to be applicable. We demonstrate such very large-scale applicability using the YFCC100M benchmark, for which we realize with a GMM of up to 50.000 clusters an optimization of a data density model with up to 150 M parameters. [ABSTRACT FROM AUTHOR]

Adversarial attacks have been extensively studied in recent years since they can identify the vulnerability of deep learning models before deployed. In this paper, we consider the black-box adversarial setting, where the adversary needs to craft adversarial examples without access to the gradients of a target model. Previous methods attempted to approximate the true gradient either by using the transfer gradient of a surrogate white-box model or based on the feedback of model queries. However, the existing methods inevitably suffer from low attack success rates or poor query efficiency since it is difficult to estimate the gradient in a high-dimensional input space with limited information. To address these problems and improve black-box attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling and gradient averaging, respectively. Our methods can take the advantage of a transfer-based prior given by the gradient of a surrogate model and the query information simultaneously. Through theoretical analyses, the transfer-based prior is appropriately integrated with model queries by an optimal coefficient in each method. Extensive experiments demonstrate that, in comparison with the alternative state-of-the-arts, both of our methods require much fewer queries to attack black-box models with higher success rates. [ABSTRACT FROM AUTHOR]

In this article, we consider an iterative adaptive dynamic programming (ADP) algorithm within the Hamiltonian-driven framework to solve the Hamilton–Jacobi–Bellman (HJB) equation for the infinite-horizon optimal control problem in continuous time for nonlinear systems. First, a novel function, “min-Hamiltonian,” is defined to capture the fundamental properties of the classical Hamiltonian. It is shown that both the HJB equation and the policy iteration (PI) algorithm can be formulated in terms of the min-Hamiltonian within the Hamiltonian-driven framework. Moreover, we develop an iterative ADP algorithm that takes into consideration the approximation errors during the policy evaluation step. We then derive a sufficient condition on the iterative value gradient to guarantee closed-loop stability of the equilibrium point as well as convergence to the optimal value. A model-free extension based on an off-policy reinforcement learning (RL) technique is also provided. Finally, numerical results illustrate the efficacy of the proposed framework. [ABSTRACT FROM AUTHOR]

This article presents a rough-to-fine evolutionary multiobjective optimization algorithm based on the decomposition for solving problems in which the solutions are initially far from the Pareto-optimal set. Subsequently, a tree is constructed by a modified $k$ -means algorithm on $N$ uniform weight vectors, and each node of the tree contains a weight vector. Each node is associated with a subproblem with the help of its weight vector. Consequently, a subproblem tree can be established. It is easy to find that the descendant subproblems are refinements of their ancestor subproblems. The proposed algorithm approaches the Pareto front (PF) by solving a few subproblems in the first few levels to obtain a rough PF and gradually refining the PF by involving the subproblems level-by-level. This strategy is highly favorable for solving problems in which the solutions are initially far from the Pareto set. Moreover, the proposed algorithm has lower time complexity. Theoretical analysis shows the complexity of dealing with a new candidate solution is $\mathcal {O}(M \log N)$ , where $M$ is the number of objectives. Empirical studies demonstrate the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Although cell-free massive multiple-input–multiple-output (mMIMO) Internet-of-Things (IoT) systems can improve spectral efficiency (SE) significantly compared with conventional cellular mMIMO IoT systems due to high coverage and no intercell interference, the pilot contamination and active sensors (ASs) interference can still seriously limit the further improvement of SE. In this article, we first develop a model of the cell-free mMIMO IoT system and then derive a mathematical expression of the SE to formulate a maximized sum SE optimization problem for jointly controlling pilot and data power. This problem is nonconvex; thus, a successive convex approximation (SCA) iteration algorithm is proposed, which, in fact, approximates the objective and constraint function in each iteration, and converts the initial optimization problem into an easy-to-solve geometric programming (GP) problem. Finally, simulation results show that our proposed algorithm outperforms the existing algorithms related to power control optimization in terms of the sum SE performance. [ABSTRACT FROM AUTHOR]

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and the scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy-tensor estimating error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy. [ABSTRACT FROM AUTHOR]

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e., $2\times 2$ 2 × 2 bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage. [ABSTRACT FROM AUTHOR]

Owing to its good compression ability, discrete cosine transform (DCT) is widely used in signal processing, including high-efficiency video coding (HEVC). For efficient implementation, approximate DCTs and integer DCTs were proposed, but the challenge in the tradeoff between coding performance and implementation cost always exists. To solve this problem, this article proposes a new algorithm to derive Int-DCT with good coding performance and low hardware cost. To address the multiobjective optimization problem, we extract information from the initially shortlisted transform matrices to derive the weighting factors for the different matrices properties. Those properties having a higher impact to the performance are assigned with higher weights and vice versa. Subsequently, an efficient search algorithm is proposed to shortlist those candidates which can lead to better coding performance evaluated by the proposed measure. Last but not the least, a splitting method is proposed to search the efficient extended double-base number system (EDBNS) representation of the coefficients for hardware implementation and select the solution which encounters the lowest cost. The experimental results in ASIC demonstrate that the implementation area and power cost of designs by the new algorithm are reduced by at least 11.1% and 17.5% for 32-point transform, respectively, over other competing algorithms. Meanwhile, the transforms generated by the proposed algorithm causes negligible impact to coding performance compared to the original transforms in HEVC. [ABSTRACT FROM AUTHOR]

One of the most extensively studied combinatorial optimization problems is the Travelling Salesman Problem (TSP). Considerable research efforts in the past have resulted in exact solvers. However, the runtime of such hand-crafted solutions increases exponentially with problem size. Ising model based solvers have also gained prominence due to their abilities to find fast and approximate solutions for combinatorial optimization problems. However, such Ising based heuristics also suffer from scalability as the solution quality becomes increasingly sub-optimal with increase in problem size. In this work, we propose Neuro-Ising – a machine learning framework which uses Ising models to find clusters of near-optimal partial solutions of large scale TSPs and combines those solutions by employing a supervised data driven mechanism, which we model as a Graph Neural Network (GNN). The GNN is trained from solution instances obtained through exact solvers and hence, the proposed approach generalizes to unseen problems while avoiding the run-time complexity otherwise required, if the solution is built from scratch. Using standard computing resources, our proposed framework rapidly converges to near-optimal solutions for 15 TSPs (upto $\sim 5k$ cities) from the TSPLib benchmark suite. We report $\sim 10.66\times $ speedup over Tabu Search for 8 problems. Furthermore, compared to two state-of-the-art clustering-based TSP solvers, Neuro-Ising achieves $\sim 38 \times $ faster convergence along with $\sim 8.9\%$ better quality of solution, on average. [ABSTRACT FROM AUTHOR]

We propose a novel semi-supervised learning (SSL) assumption—the high separation probability (HSP) assumption—that is complementary to the common low density separation (LDS) assumption, and a highly accurate and efficient SSL algorithm, the transductive minimax probability machine (TMPM). Under the HSP assumption, a preferred classifier should ensure that with high probability the samples are far away from the decision boundary. Similarly, the LDS assumption states that the decision boundary should lie in a low-density region. A remarkable property of HSP is that it provides an elegant theoretical framework for analyzing the generalization performance of SSL, while it remains difficult for the LDS assumption to have a quantitative criterion on how it fits the data. Moreover, it has the same paradigm as the minimax probability machine (MPM) and yields an intractable mixed-integer optimization for solving the transductive label assignment problem. Consequently, we propose TMPM with a label-switching strategy and iterative manner to formalize our approximate solution. Theoretically, we analyze the computational complexity, convergence property, and generalization error bound of TMPM. Empirically, we show that TMPM achieves competitive performance on a wide range of datasets, while being almost one order of magnitude faster than existing SSL approaches. [ABSTRACT FROM AUTHOR]

This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. Typically, the performance of TD(0) and TD($\lambda$ λ ) is very sensitive to the choice of stepsizes. Oftentimes, TD(0) suffers from slow convergence. Motivated by the tight link between the TD(0) learning algorithm and the stochastic gradient methods, we develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation that we term AdaTD(0). In contrast to the TD(0), AdaTD(0) is robust or less sensitive to the choice of stepsizes. Analytically, we establish that to reach an $\epsilon$ ε accuracy, the number of iterations needed is $\tilde{O}(\epsilon ^{-2}\ln ^4\frac{1}{\epsilon }/\ln ^4\frac{1}{\rho })$ O ˜ (ε - 2 ln 4 1 ε / ln 4 1 ρ) in the general case, where $\rho$ ρ represents the speed of the underlying Markov chain converges to the stationary distribution. This implies that the iteration complexity of AdaTD(0) is no worse than that of TD(0) in the worst case. When the stochastic semi-gradients are sparse, we provide theoretical acceleration of AdaTD(0). Going beyond TD(0), we develop an adaptive variant of TD($\lambda$ λ ), which is referred to as AdaTD($\lambda$ λ ). Empirically, we evaluate the performance of AdaTD(0) and AdaTD($\lambda$ λ ) on several standard reinforcement learning tasks, which demonstrate the effectiveness of our new approaches. [ABSTRACT FROM AUTHOR]

This article deals with nonconvex stochastic optimization problems in deep learning. Appropriate learning rates, based on theory, for adaptive-learning-rate optimization algorithms (e.g., Adam and AMSGrad) to approximate the stationary points of such problems are provided. These rates are shown to allow faster convergence than previously reported for these algorithms. Specifically, the algorithms are examined in numerical experiments on text and image classification and are shown in experiments to perform better with constant learning rates than algorithms using diminishing learning rates. [ABSTRACT FROM AUTHOR]

This article introduces a new deep learning approach to approximately solve the covering salesman problem (CSP). In this approach, given the city locations of a CSP as input, a deep neural network model is designed to directly output the solution. It is trained using the deep reinforcement learning without supervision. Specifically, in the model, we apply the multihead attention (MHA) to capture the structural patterns, and design a dynamic embedding to handle the dynamic patterns of the problem. Once the model is trained, it can generalize to various types of CSP tasks (different sizes and topologies) without the need of retraining. Through controlled experiments, the proposed approach shows desirable time complexity: it runs more than 20 times faster than the traditional heuristic solvers with a tiny gap of optimality. Moreover, it significantly outperforms the current state-of-the-art deep learning approaches for combinatorial optimization in the aspect of both training and inference. In comparison with traditional solvers, this approach is highly desirable for most of the challenging tasks in practice that are usually large scale and require quick decisions. [ABSTRACT FROM AUTHOR]

This article proposes robust inverse $Q$ -learning algorithms for a learner to mimic an expert’s states and control inputs in the imitation learning problem. These two agents have different adversarial disturbances. To do the imitation, the learner must reconstruct the unknown expert cost function. The learner only observes the expert’s control inputs and uses inverse $Q$ -learning algorithms to reconstruct the unknown expert cost function. The inverse $Q$ -learning algorithms are robust in that they are independent of the system model and allow for the different cost function parameters and disturbances between two agents. We first propose an offline inverse $Q$ -learning algorithm which consists of two iterative learning loops: 1) an inner $Q$ -learning iteration loop and 2) an outer iteration loop based on inverse optimal control. Then, based on this offline algorithm, we further develop an online inverse $Q$ -learning algorithm such that the learner mimics the expert behaviors online with the real-time observation of the expert control inputs. This online computational method has four functional approximators: a critic approximator, two actor approximators, and a state-reward neural network (NN). It simultaneously approximates the parameters of $Q$ -function and the learner state reward online. Convergence and stability proofs are rigorously studied to guarantee the algorithm performance. [ABSTRACT FROM AUTHOR]

Automated hyperparameter optimization (HPO) has gained great popularity and is an important component of most automated machine learning frameworks. However, the process of designing HPO algorithms is still an unsystematic and manual process: new algorithms are often built on top of prior work, where limitations are identified and improvements are proposed. Even though this approach is guided by expert knowledge, it is still somewhat arbitrary. The process rarely allows for gaining a holistic understanding of which algorithmic components drive performance and carries the risk of overlooking good algorithmic design choices. We present a principled approach to automated benchmark-driven algorithm design applied to multifidelity HPO (MF-HPO). First, we formalize a rich space of MF-HPO candidates that includes, but is not limited to, common existing HPO algorithms and then present a configurable framework covering this space. To find the best candidate automatically and systematically, we follow a programming-by-optimization approach and search over the space of algorithm candidates via Bayesian optimization. We challenge whether the found design choices are necessary or could be replaced by more naive and simpler ones by performing an ablation analysis. We observe that using a relatively simple configuration (in some ways, simpler than established methods) performs very well as long as some critical configuration parameters are set to the right value. [ABSTRACT FROM AUTHOR]

Broadcasting is an essential operation in wireless networks for disseminating the message from the source node to all other nodes. Unfortunately, the problem of Minimum Latency Broadcast Scheduling (MLBS) in duty-cycled wireless sensor networks is not well studied. In existing works, the construction of broadcast tree and the scheduling of transmissions are conducted separately, where a tree-based structure is used as the input of the scheduling algorithm. Relying on a pre-determined tree may result in a much large latency even using the optimal scheduling method. Thus, the MLBS problem in duty-cycled WSNs without the above limitation is investigated in this paper. First, to avoid relying on a pre-determined structure, a two-step scheduling algorithm is proposed to construct the broadcast tree and compute a collision-free schedule simultaneously. To the best of our knowledge, this is the first work that can integrate these two kinds of operations together. Second, a novel transmission mode, i.e., concurrent broadcasting, is first introduced for wireless networks and several techniques are designed to further improve the broadcast latency. Third, the multiple messages broadcasting and all-to-all broadcasting algorithms, which can generate a series of broadcast schedules independently without a pre-determined tree, are also proposed by taking care of the collisions in both the current and the previous broadcast schedules. Finally, the theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in terms of latency. [ABSTRACT FROM AUTHOR]

Provisioning reliable network services for mobile users in edge computing environments is the top priority of network service providers, as unreliable services will result in tremendous losses of revenues and customers. In this paper, we study a novel service reliability augmentation problem in a mobile edge computing (MEC) network, where mobile users request network services with service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant virtualized network function (VNF) instance placement in case the primary VNF instance fails. We aim to augment the service reliability of each admitted request to its specified reliability expectation, subject to computing capacity on each cloudlet. To this end, we first formulate a novel service reliability augmentation problem for each request with an SFC and a reliability expectation requirement, by augmenting its reliability through redundant VNF instance deployment. We then show that the problem is NP-hard, and provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets. We then deal with the service reliability augmentation problem of an admitted request under the assumption that all secondary VNF instances of each primary VNF instance must be placed into the cloudlets no more than $l$ l hops from the cloudlet of its primary VNF instance for a fixed $l$ l with $1\leq l \leq n-1$ 1 ≤ l ≤ n - 1 , where $n$ n is the number of cloudlets in the network, for which we formulate an integer linear program solution, and develop a randomized algorithm with a good approximation ratio and high probability, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We third study the service reliability augmentation problem for a set of admitted requests by extending the proposed algorithm for the service reliability augmentation problem for a single request admission. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts. [ABSTRACT FROM AUTHOR]

Focusing on the performance deterioration of nonlinear filtering algorithms in the error-in-variable (EIV) model, a nonlinear version of maximum total correntropy (MTC) algorithm called kernel recursive maximum total correntropy (KRMTC) is proposed in this brief, which constructs a nonlinear relationship based on MTC criterion between inputs and outputs in high-dimensional feature space. Compared with existing kernel adaptive filtering (KAF) algorithms based on traditional mean square error (MSE) and maximum correntropy criteria (MCC), the proposed algorithm can handle nonlinear modeling problems in the EIV model well. In addition, an approximate linear dependency (ALD) criterion is applied to reduce the computational complexity of KRMTC. To verify the feasibility of the proposed algorithm, firstly, the convergence of the KRMTC algorithm under some assumptions is discussed and its local convergence condition is given. Secondly, the proposed algorithm is applied to the Lorenz time-series prediction and wind prediction simulations. Simulation results display that the KRMTC algorithm has better performance than kernel recursive least squares (KRLS) and kernel recursive maximum correntropy (KRMC) algorithms in EIV case. [ABSTRACT FROM AUTHOR]

This article presents a simple yet effective method for computing geodesic distances on triangle meshes. Unlike the popular window propagation methods that partition mesh edges into intervals of varying lengths, our method places evenly-spaced, source-independent Steiner points on edges. Given a source vertex, our method constructs a Steiner-point graph that partitions the surface into mutually exclusive tracks, called geodesic tracks. Inside each triangle, the tracks form sub-regions in which the change of distance field is approximately linear. Our method does not require any pre-computation, and can effectively balance speed and accuracy. Experimental results show that with 5 Steiner points on each edge, the mean relative error is less than 0.3 $\%$ % for common 3D models used in the graphics community. We propose a set of effective filtering rules to eliminate a large amount of useless broadcast events. For a 1000K-face model, our method runs 10 times faster than the conventional Steiner point method that examines a complete graph of Steiner points in each triangle. We also observe that using more Steiner points increases the accuracy at only a small extra computational cost. Our method works well for meshes with poor triangulation and non-manifold configuration, which often poses challenges to the existing PDE methods. We show that geodesic tracks, as a new data structure that encodes rich information of discrete geodesics, support accurate geodesic path and isoline tracing, and efficient distance query. Our method can be easily extended to meshes with non-constant density functions and/or anisotropic metrics. [ABSTRACT FROM AUTHOR]

Graph burning is a process to determine the spreading of information in a graph. If a sequence of vertices burns all the vertices of a graph by following the graph burning process, then such a sequence is known as a burning sequence. The graph burning problem consists in finding a minimum length burning sequence for a given graph. The solution to this NP-hard combinatorial optimization problem helps quantify a graph’s vulnerability to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over arbitrary graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in $O(n^{3})$ steps and has a tight approximation factor of $3-2/b(G)$ , where $b(G)$ is the size of an optimal solution. The main attribute of BFF is that it has a better approximation factor than the state-of-the-art approximation algorithms for arbitrary graphs, which report an approximation factor of 3. Despite being simple, BFF proved practical when tested over some benchmark datasets.

A subset ${\mathcal{ S}}\subseteq V$ of vertices of an undirected graph $G=(V,E)$ is a hub cover when for each edge $(u,v) \in E$ , at least one of its endpoints belongs to ${\mathcal{ S}}$ , or there exists a vertex $r \in {\mathcal{ S}}$ that is a neighbor of both $u$ and $v$ . The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes $\Psi $ -MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is $\ln \mu $ , where $\mu $ is upper bounded by $\min \left\{{\frac {1}{2}(\Delta +1)^{2}, \vert E\vert }\right\}$ and $\Delta $ is the degree of $G$ . The execution time of $\Psi $ -MHC is $O((\Delta + 1) \vert E \vert + \vert {\mathcal{ S}} \vert \vert V \vert)$ . Experimental results show that $\Psi $ -MHC far outperforms the theoretical approximation ratio for the input graph instances.

Many inverse problems in machine learning, system identification, and image processing include nuisance parameters, which are important for the recovering of other parameters. Separable nonlinear optimization problems fall into this category. The special separable structure in these problems has inspired several efficient optimization strategies. A well-known method is the variable projection (VP) that projects out a subset of the estimated parameters, resulting in a reduced problem that includes fewer parameters. The expectation maximization (EM) is another separated method that provides a powerful framework for the estimation of nuisance parameters. The relationships between EM and VP were ignored in previous studies, though they deal with a part of parameters in a similar way. In this article, we explore the internal relationships and differences between VP and EM. Unlike the algorithms that separate the parameters directly, the hierarchical identification algorithm decomposes a complex model into several linked submodels and identifies the corresponding parameters. Therefore, this article also studies the difference and connection between the hierarchical algorithm and the parameter-separated algorithms like VP and EM. In the numerical simulation part, Monte Carlo experiments are performed to further compare the performance of different algorithms. The results show that the VP algorithm usually converges faster than the other two algorithms and is more robust to the initial point of the parameters. [ABSTRACT FROM AUTHOR]

The vehicular sensor network (VSN) is a bright candidate for many applications owing to its particular advantages. Such an application is air pollution monitoring, a critical issue associated directly with public health. We also notice that public transports are well-suited to deploy the network for this type of application. In this article, we propose a practical approach that leverages public buses to build the vehicle network with attached sensors for air pollution monitoring toward minimizing the deployment cost. Therefore, we hereafter call this problem vehicular sensor deployment (VSD). We first convert the VSD issue to a flow network described by a directed graph. Then, based on air sampling requirements, capacity constraints, and flow conservation of the flow network, we formulate the problem as an integer linear programming (ILP) model that yields the optimal solution. In addition, we suggest an approximation algorithm implemented by the linear programming relaxation technique combined with the randomized rounding algorithm (LPR-RRA), which provides approximate solutions to large-scale VSD problems. We also propose a greedy-based algorithm (GBA) to solve the problem against the most effective sampling in each iteration. Finally, we conduct experiments to evaluate the performance of the proposed algorithms as well as the influences of associated factors on the deployment cost. Simulation results show that the approximation algorithm approaches the optimal and outperforms the greedy. [ABSTRACT FROM AUTHOR]

Multi-scale exposure fusion (MEF) is an efficient way to fuse differently exposed low dynamic range (LDR) images of a high dynamic range (HDR) scene into an information enriched LDR image. In this paper, a new MEF algorithm is proposed to merge the differently exposed LDR images by introducing novel content adaptive edge-preserving smoothing (CAS) pyramids for the weight maps of all the LDR images. With the proposed CAS pyramids, details in the brightest and darkest regions of the HDR scene are preserved better than existing MEF algorithms on top of the Gaussian pyramids and edge-preserving smoothing pyramids. Comparisons experimentally demonstrate the effectiveness of the proposed algorithm to nine state-of-the-art MEF algorithms from both subjective and objective points of view regardless the image sizes. [ABSTRACT FROM AUTHOR]

This article studies the mean standard deviation (mean-std) Canadian traveller problem (CTP). Different from the canonical CTP, which aims at minimizing the traveller's expected travel time, while considering edge breakdown probabilities, we introduce the reliability version of CTP, which tries to find a routing policy with the minimal linear combination of the travel time's mean and standard deviation. With the recent development of internet-of-things (IoT) technology, the transportation network's edges' travel-time statistics, i.e., mean and standard deviation, as well as the traversal probabilities, are available to the end users. With those information, we propose a dual dynamic programming (DDP) method, which simultaneously estimates the first-order and the second-order moments of a given decision-list (DL) policy, and thereby makes improvements towards to the optimal one through the generalized policy iteration (GPI) scheme. We construct an open source benchmark environment to evaluate the performance of different mean-std CTP solutions, and show that the DDP method outperforms state of the arts in a range of transportation networks. [ABSTRACT FROM AUTHOR]

In the phase retrieval problem one seeks to recover an unknown $n$ dimensional signal vector $\mathbf {x}$ from $m$ measurements of the form $y_{i} = |(\mathbf {A} \mathbf {x})_{i}|$ , where $\mathbf {A}$ denotes the sensing matrix. Many algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix $\mathbf {A}$ is generated by sub-sampling $n$ columns of a uniformly random (i.e., Haar distributed) orthogonal matrix, in the high dimensional asymptotic regime ($m,n \rightarrow \infty, n/m \rightarrow \kappa $), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For a special class of linearized message-passing algorithms, we show that the state evolution is universal: it continues to hold even when $\mathbf {A}$ is generated by randomly sub-sampling columns of the Hadamard-Walsh matrix, if the signal is drawn from a Gaussian prior. [ABSTRACT FROM AUTHOR]

As the artificial intelligence and Internet of Things (AIoT) develop rapidly, the deployment of artificial neural networks in edge computing is becoming significant with great challenge. The binarized convolutional neural network (BCNN) is one of the most widely adopted light-weight ANNs in AIoT, which can achieve the balance of system accuracy and hardware resource consumption, compared to others. To achieve high power and area efficiency in BCNN deployment, many approximate computing (AxC) techniques are integrated to make full use of the resilience of BCNN. As the research focused on the integration of AxC in circuit design, the design of AxC itself is not fully considered when applied to specific applications or domains. Based on circuit-architecture-system co-design, this article proposes an efficient BCNN deployment method, including a quality-circuit co-design method for approximate adder generation, a quality-aware intercompensation approach for addition tree, and a computing quality involved retraining approach for BCNN deployment. Experimental results show that the proposed quality model can achieve 86.43% in average accuracy while evaluating nine types of typical approximate adders. The proposed method is conducted on the applications of keyword spotting of GSCD, MNIST, and CIFAR-10, and we can further rise the approximation degree by 50%–75%, while reducing the accuracy by less than 1%. [ABSTRACT FROM AUTHOR]

Approximate computing is an attractive paradigm for reducing the design complexity of error-resilient systems, therefore, improving performance and saving power consumption. In this work, we propose a new two-level approximate logic synthesis method based on cube insertion and removal procedures. The experimental results have shown significant literal count and runtime reduction compared to the state-of-the-art approach. The method scalability is illustrated for a high error threshold over large benchmark circuits. The obtained solutions have presented a literal number reduction up to 38%, 56%, and 93% with respect to an error rate of 1%, 3%, and 5%, respectively. [ABSTRACT FROM AUTHOR]

Symbol detection (SD) plays an important role in a digital communication system. However, most SD algorithms require channel state information (CSI), which is often difficult to estimate accurately. As a consequence, it is challenging for these SD algorithms to approach the performance of the maximum likelihood detection (MLD) algorithm. To address this issue, we employ both semi-supervised learning and ensemble learning to design a flexible parallelizable approach in this paper. First, we prove theoretically that the proposed algorithms can arbitrarily approach the performance of the MLD algorithm with perfect CSI. Second, to enable parallel implementation and also enhance design flexibility, we further propose a parallelizable approach for multi-output systems. Finally, comprehensive simulation results are provided to demonstrate the effectiveness and superiority of the designed algorithms. In particular, the proposed algorithms approach the performance of the MLD algorithm with perfect CSI, and outperform it when the CSI is imperfect. Interestingly, a detector constructed with received signals from only two receiving antennas (less than the size of the whole receiving antenna array) can also provide good detection performance. [ABSTRACT FROM AUTHOR]

Online streaming feature selection (OSFS) has attracted extensive attention during the past decades. Current approaches commonly assume that the feature space of fixed data instances dynamically increases without any missing data. However, this assumption does not always hold in many real applications. Motivated by this observation, this study aims to implement online feature selection from sparse streaming features, i.e., features flow in one by one with missing data as instance count remains fixed. To do so, this study proposes a latent-factor-analysis-based online sparse-streaming-feature selection algorithm (LOSSA). Its main idea is to apply latent factor analysis to pre-estimate missing data in sparse streaming features before conducting feature selection, thereby addressing the missing data issue effectively and efficiently. Theoretical and empirical studies indicate that LOSSA can significantly improve the quality of OSFS when missing data are encountered in target instances. [ABSTRACT FROM AUTHOR]