Lagrangean Based Methods for Solving Large-Scale Cellular Network Design Problems

The cellular network design (CND) problem is formulated as a comprehensive linear mixed integer programming model integrating the base station location (BSL) problem, the frequency channel assignment (FCA) problem and the topological network design (TND) problem. A solution algorithm based on Lagrangean relaxation is proposed for solving this complex cellular network design problem. Pursuing the optimum solution through exact algorithms to this problem appears to be unrealistic considering the large scale nature and NP-hardness of the problem. Therefore, the solution algorithm strategy consists in computing effective lower and upper bounds for the problem. Lower bounds are evaluated through a Lagrangean relaxation technique and subgradient method. A Lagrangean heuristic is developed to compute upper bounds based on the Lagrangean solution. The bounds are improved through a customized branch and bound algorithm which takes in account specific knowledge of the problem to improve its efficiency. Thirty two random test instances are solved using the proposed algorithm and the CPLEX optimization package. The results show that the duality gap is excessive, so it cannot guarantee the quality of the solution. However, the proposed algorithm provides optimal or near optimal solutions for the problem instances for which CPLEX also provides the optimal solution. It further suggests that the proposed algorithm provides optimal or near optimal solutions for the other instances too. Finally, the results demonstrate that the proposed algorithm is superior to CPLEX as a solution approach for the CND problem.     

Bayesian Sparse Reconstruction Method of Compressed Sensing in the Presence of Impulsive Noise

The majority of existing recovery algorithms in the framework of compressed sensing are not robust to the impulsive noise. However, the impulsive noise is always present in the actual communication and signal processing system. In this paper, we propose a method named ‘Bayesian sparse reconstruction’ to recover the sparse signal from the measurement vector which is corrupted by the impulsive noise. The Bayesian sparse reconstruction method is composed of five parts, which are the preliminary detection of the location set of impulses, the impulsive noise fast relevance vector machine algorithm, the step of pruning, Bayesian impulse detection algorithm and the maximum a posteriori estimate of the sparse vector. The Bayesian sparse reconstruction method can achieve effective signal recovery in the presence of impulsive noise, depending on the mutual influence of the impulsive noise fast relevance vector machine algorithm, the step of pruning and the Bayesian impulse detection algorithm. Experimental results show that the Bayesian sparse reconstruction method is robust to the impulsive noise and effective in the additive white Gaussian noise environment.     

基于自适应滤波的压缩感知重构方法

自适应滤波框架中,滤波器的抽头系数可以利用特定的自适应算法达到近似维纳解,从而使滤波器的输出误差达到最小.将这个框架应用到压缩感知重构信号中,信号的稀疏系数等效为滤波器系数权值向量,从而可获得最佳的稀疏系数,以高概率重构信号.本文介绍了已有学者研究出的一种L0最小均方算法(L0-LMS),该算法中引入零引力项加快了权矢量向稀疏解收敛的速度,保证解的稀疏性.通过仿真可知,基于自适应滤波算法重构稀疏信号的性能较好,甚至优于压缩感知中常用的OMP算法.     

多变量时间序列中基于克罗内克压缩感知的缺失数据预测算法

针对现有算法在预测多变量时间序列中的缺失数据时不适用或只适用于缺失数据较少的情况,该文提出一种基于克罗内克压缩感知的缺失数据预测算法。首先,利用多变量时间序列的时域平滑特性和序列之间的潜在相关性从时空两个方面设计了稀疏表示基,从而将缺失数据预测问题建模成稀疏向量恢复问题。模型求解部分,根据缺失数据的位置特点设计了适合当前应用场景且与稀疏表示基相关性低的观测矩阵。接着,从稀疏表示向量是否足够稀疏和感知矩阵是否满足有限等距特性两个方面验证了模型的性能。最后,仿真结果表明,所提算法在数据缺失严重的情况下具有良好的性能。     

空间连接处理中提炼步骤的遗传优化

内务处理是用来优化空间连接处理提炼步骤的I/O代价,属于NP-难的问题,现有求解方法复杂度太高.本文将页面聚簇和聚簇调度问题分别归约为图的k划分和最长路径问题,提出了改进的遗传算法和基于最大生成树的近似算法进行求解.对经典遗传算法的进行了修正以满足页面聚簇划分约束.近似算法的解大于最优解的一半.理论分析和仿真实验验证了算法的可行性和有效性.     

应用于非负稀疏信号重构的交替方向乘子法

非负稀疏信号在欠定线性观测条件下的重构效果不理想,仍有进一步提高的余地。文中将非负稀疏信号重构建模为线性规划问题,在交替方向乘子法的框架下得到了具有闭合解形式的优化算法,且算法复杂度较低。为了进一步增强重构信号的稀疏性,提出了迭代加权线性规划算法,通过对权值向量和重构信号交替优化提高了重构准确率。实验仿真验证了算法的有效性,针对随机生成信号和实际语音能量谱这两类非负稀疏信号均取得了较好的重构效果,重构性能优于目前一些流行的稀疏重构算法。      

Sparse least mean fourth algorithm for adaptive channel estimation in low signal‐to‐noise ratio region

Both least mean square (LMS) and least mean fourth (LMF) are popular adaptive algorithms with application to adaptive channel estimation. Because the wireless channel vector is often sparse, sparse LMS‐based approaches have been proposed with different sparse penalties, for example, zero‐attracting LMS and L_p‐norm LMS. However, these proposed methods lead to suboptimal solutions in low signal‐to‐noise ratio (SNR) region, and the suboptimal solutions are caused by LMS‐based algorithms that are sensitive to the scaling of input signal and strong noise. Comparatively, LMF can achieve better solution in low SNR region. However, LMF cannot exploit the sparse information because the algorithm depends only on its adaptive updating error but neglects the inherent sparse channel structure. In this paper, we propose several sparse LMF algorithms with different sparse penalties to achieve better solution in low SNR region and take the advantage of channel sparsity at the same time. The contribution of this paper is briefly summarized as follows: (1) construct the cost functions of the LMF algorithm with different sparse penalties; (2) derive their lower bounds; and (3) provide experiment results to show the performance advantage of the propose method in low SNR region. Copyright © 2013 John Wiley & Sons, Ltd.     

Multiterminal net routing for partial crossbar-based multi-FPGA systems

Multi-FPGA (field-programmable gate arrays) systems are used as custom computing machines to solve compute-intensive problems and also in the verification and prototyping of large circuits. In this paper, we address the problem of routing multiterminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multiterminal routing problem as a partitioned bin-packing problem and formulate it as an integer linear programming problem where the number of variables is exponential. A fast heuristic is applied to compute an upper bound on the routing solution. Then, a column generation technique is used to solve the linear relaxation of the initial master problem in order to obtain a lower bound on the routing solution. This is followed by an iterative branch-and-price procedure that attempts to find a routing solution somewhere between the two established bounds. In this regard, the proposed algorithm guarantees an exact-routing solution by searching a branch-and-price tree. Due to the tightness of the bounds, the branch-and-price tree is small resulting in shorter execution times. Experimental results are provided for different netlists and board configurations in order to demonstrate the algorithms performance. The obtained results show that the algorithm finds an exact routing solution in a very short time.     

A parallel finite-element tearing and interconnecting algorithm forsolution of the vector wave equation with PML absorbing medium

A domain decomposition method based on the finite-element tearing and interconnecting (FETI) algorithm is presented for the solution of the large sparse matrices associated with the finite-element method (FEM) solution of the vector wave equation. The FETI algorithm is based on the method of Lagrange multipliers and leads to a reduced-order system, which is solved using the biconjugate gradient method (BiCGM). It is shown that this method is highly scalable and is more efficient on parallel platforms when solving large matrices than traditional iterative methods such as a preconditioned conjugate gradient algorithm. This is especially true when a perfectly matched layer (PML) absorbing medium is used to terminate the problem domain     

Sparse solutions to linear inverse problems with multiple measurement vectors

We address the problem of finding sparse solutions to an underdetermined system of equations when there are multiple measurement vectors having the same, but unknown, sparsity structure. The single measurement sparse solution problem has been extensively studied in the past. Although known to be NP-hard, many single-measurement suboptimal algorithms have been formulated that have found utility in many different applications. Here, we consider in depth the extension of two classes of algorithms-Matching Pursuit (MP) and FOCal Underdetermined System Solver (FOCUSS)-to the multiple measurement case so that they may be used in applications such as neuromagnetic imaging, where multiple measurement vectors are available, and solutions with a common sparsity structure must be computed. Cost functions appropriate to the multiple measurement problem are developed, and algorithms are derived based on their minimization. A simulation study is conducted on a test-case dictionary to show how the utilization of more than one measurement vector improves the performance of the MP and FOCUSS classes of algorithm, and their performances are compared.     

An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem

A tabu search algorithm with a dynamic tabu list for the fixed-spectrum frequency-assignment problem is presented. For cellular problems, the algorithm can be combined with an efficient cell reoptimization step. The algorithm is tested on several sets of test problems and compared with existing algorithms of established performance. In particular, it is used to improve some of the best existing assignments for COST 259 benchmarks. These results add support to the claim that the algorithm is the most effective available, at least when solution quality is a more important criterion than solution speed. The algorithm is robust and easy to tune.     

Solution of inverse problems in image processing by waveletexpansion

We describe a wavelet-based approach to linear inverse problems in image processing. In this approach, both the images and the linear operator to be inverted are represented by wavelet expansions, leading to a multiresolution sparse matrix representation of the inverse problem. The constraints for a regularized solution are enforced through wavelet expansion coefficients. A unique feature of the wavelet approach is a general and consistent scheme for representing an operator in different resolutions, an important problem in multigrid/multiresolution processing. This and the sparseness of the representation induce a multigrid algorithm. The proposed approach was tested on image restoration problems and produced good results.     

基于模拟退火算法的平面稀疏阵优化

大规模稀疏阵列优化时,解空间十分庞大,一般优化算法难以实现.模拟退火算法不是一种解空间遍历算法,因而非常适合用于解决此类问题.利用平面阵的对称性,对解空间进行镜像压缩,进一步提高了优化效率.利用解空间压缩后的模拟退火算法优化得到了一种副瓣特性优良的稀疏布阵方式.     

基于函数复杂度的自适应模拟退火和禁忌搜索新算法

在求解多峰复杂函数的过程中,传统的模拟退火算法和禁忌搜索算法经常出现算法快速收敛于局部最优解、后期收敛速度变慢和搜索能力变差等问题.为解决这些问题,本文给出函数复杂度的定义,并提出基于函数复杂度的自适应模拟退火和禁忌搜索算法.该算法首先根据函数复杂度自适应调整步长控制参数,然后根据调整后步长求得函数的粗糙解,在此基础上再使用初始步长求得全局最优解.实验表明,该算法不仅可以跳出局部最优解的限制,并且减少了迭代次数,有效地提高了全局和局部搜索能力.     

一种基于稀疏分解的窄带信号频率估计算法

针对窄带多分量信号频率估计问题,该文提出一种基于稀疏分解的频率估计算法,能够同时对多个窄带信号的频率进行估计。首先利用传统方法进行频率预估计,然后根据频率预估计的结果建立冗余字典,对信号进行稀疏表示,最后通过匹配追踪算法得到精确的频率估计。该算法极大地减小了字典的长度和稀疏分解的运算量,而且在迭代过程中利用了全局信息更新残差向量,估计结果更为精确,在低信噪比情况下性能也较为稳健。仿真结果验证该算法的有效性和正确性。     

一种基于改进PDR与外部位置信息的融合定位算法

针对传统行人航位推算(PDR)算法在手机倾斜程度较大时定位误差大且定位误差随步数累积的问题,提出一种改进PDR定位与外部位置信息融合的定位算法。算法首先估计手机姿态矩阵并利用姿态矩阵旋转加速度、角速度与磁感应强度的测量向量。再利用旋转后的加速度向量进行步伐探测、步频步长估计;旋转后的角速度与磁感应强度向量进行方向角估计。最后根据PDR定位结果与外部位置信息的误差特性,通过比例积分(PI)控制器进行融合定位并反馈调节步长模型参数。实验表明算法中传感器测量向量旋转、融合定位和步长模型参数反馈调整有效减小了算法的定位误差,定位轨迹更接近于真实行进轨迹。     

协方差矩阵稀疏表示在网格失配波达方向估计中的应用

该文利用了入射信号在空域的稀疏性,将波达方向（DOA）估计问题描述为在网格划分的空间协方差矩阵稀疏表示模型,并将其松弛为一个凸问题,从而提出了一种网格匹配下的交替迭代方法（AIEGM）。传统的基于稀疏重构的波达方向估计算法由于其模型的局限性,一旦入射角不在预先设定的离散化网格上,就会造成估计性能的急剧恶化。针对这个问题,该算法可以在离散化网格比较粗糙的前提下,通过交替迭代的方法求解一系列基追踪去噪（BPDN）问题,对于不在网格上的真实角度估计值进行修正,从而达到更精确的波达方向估计。仿真结果证明了AIEGM算法的有效性。      

An algorithm for determination of the amplitudes of reflected and transmitted waves in the case when counterpropagating waves are incident on a multilayer stepwise inhomogeneous structure

A simple algorithm is proposed for derivimg analytical expressions for the amplitudes of reflected and transmitted waves in the case when two 1D counterpropagating waves are incident on a multilayer stepwise inhomogeneous structure. Wave amplitudes are analytically expressed for structures consisting of three, four, and five layers. The proposed algorithm is applied to solve numerically the problem of wave propagation in an inhomogeneous structure where the wave number linearly changes along the structure’s length. The algorithm involves approximation of a smooth inhomogeneity by a step one. A criterion and conditions are obtained for the applicability of the step approximation for the investigation of wave propagation through inhomogeneous media with smoothly varying parameters. It is shown that the algorithm can be applied to problems on propagation of electromagnetic waves in the cases of the normal and oblique incidence.     

一种基于局部排序的约束稀疏编码的图像分类方法

图像分类作为计算机视觉分析领域一个重要的研究方向,其分类性能很大程度上取决于图像的特征表示.为了能够更好地进行图像分类,本文提出了一种基于局部约束稀疏编码的神经气算法（Neural Gas based Locality-constrained Sparse Coding,NGLSC）用来实现图像分类.引入局部排序适配器作为距离正则化约束项已经应用在神经气（Neural Gas,NG）的算法矢量量化中,旨在通过软竞争学习算法来弥补K均值聚类（K-means）算法的不足.在稀疏编码阶段此算法可求解得到封闭解.此外,字典更新一般由目标函数的误差项来决定,已有一些经典的算法采用这种方式更新字典.本文使用ORL数据库和COIL20数据库将所提出算法和现有算法局部约束线性编码（Locality-constrained Linear Coding,LLC）,脸元数据学习方法（Metaface Learning,MFL）进行比较.实验结果证明本文所提出的算法在图像分类上准确率可达95%以上.可以看出,本文为计算机视觉图像分类工作提供了一种有价值的解决思路.     

一种稳健的稀疏Capon波束形成算法

常规Capon波束形成算法具有相对较高的旁瓣增益,且在期望信号导向矢量存在失配时,阵列输出性能下降甚至失效。为解决这一问题,引入了稀疏约束Capon波束形成算法,该算法降低了旁瓣,对期望信号来向不确定具有一定稳健性,但在幅相误差、期望信号指向偏差等多种误差同时存在的情况下其性能下降。本文在稀疏约束Capon波束形成算法基础上,给出了一种稳健的稀疏Capon波束形成算法。该算法主要是在最差性能最优化的情况下,在稀疏Capon上增加了一个导向矢量存在偏差的约束条件。通过计算机仿真,验证了新算法在多种误差环境下的有效性与优越性。