Geometric programming duals of channel capacity and rate distortion

We show that the Lagrange dual problems of the channel capacity problem with input cost and the rate distortion problem are simple geometric programs. Upper bounds on channel capacity and lower bounds on rate distortion can be efficiently generated from their duals. For channel capacity, the geometric programming dual characterization is shown to be equivalent to the minmax Kullback-Leibler (KL) characterization in Csiszar et al. (1981). For rate distortion, the geometric programming dual is extended to rate distortion with two-sided state information. A "duality by mapping" is then given between the Lagrange dual problems of channel capacity with input cost and rate distortion, which resolves several apparent asymmetries between their primal problems in the familiar form of mutual information optimization problems. Both the primal and dual problems can be interpreted in a common framework of free energy optimization from statistical physics.     

Distributed Utility Maximization for Network Coding Based Multicasting: A Shortest Path Approach

One central issue in practically deploying network coding is the adaptive and economic allocation of network resource. We cast this as an optimization, where the net-utility—the difference between a utility derived from the attainable multicast throughput and the total cost of resource provisioning—is maximized. By employing the MAX of flows characterization of the admissible rate region for multicasting, this paper gives a novel reformulation of the optimization problem, which has a separable structure. The Lagrangian relaxation method is applied to decompose the problem into subproblems involving one destination each. Our specific formulation of the primal problem results in two key properties. First, the resulting subproblem after decomposition amounts to the problem of finding a shortest path from the source to each destination. Second, assuming the net-utility function is strictly concave, our proposed method enables a near-optimal primal variable to be uniquely recovered from a near-optimal dual variable. A numerical robustness analysis of the primal recovery method is also conducted. For ill-conditioned problems that arise, for instance, when the cost functions are linear, we propose to use the proximal method, which solves a sequence of well-conditioned problems obtained from the original problem by adding quadratic regularization terms. Furthermore, the simulation results confirm the numerical robustness of the proposed algorithms. Finally, the proximal method and the dual subgradient method can be naturally extended to provide an effective solution for applications with multiple multicast sessions.     

The dual parameterization approach to optimal least square FIRfilter design subject to maximum error constraints

This paper is concerned with the design of linear-phase finite impulse response (FIR) digital filters for which the weighted least square error is minimized, subject to maximum error constraints. The design problem is formulated as a semi-infinite quadratic optimization problem. Using a newly developed dual parameterization method in conjunction with the Caratheodory's dimensional theorem, an equivalent dual finite dimensional optimization problem is obtained. The connection between the primal and the dual problems is established. A computational procedure is devised for solving the dual finite dimensional optimization problem. The optimal solution to the primal problem can then be readily obtained from the dual optimal solution. For illustration, examples are solved using the proposed computational procedure     

Analyzing the impact of selfish behaviors of Internet users and operators

Using the price of anarchy (PA) and the price of monopoly (PM), the impact of selfish behaviors of noncooperative users and profit seeking operators respectively are studied. Although PA characterizes the impact of complete deregulation, and PM characterizes the impact of complete regulation, this paper shows that they are related as primal and dual ratios of two correlated optimization problems. An approach to derive bounds of both these ratios is proposed, and numerical bounds of both prices are derived in simple affine settings.     

Augmented Lagrangean Based Algorithms for Centralized Network Design

Capacitated spanning tree problems appear frequently as fundamental problems in many communication network design problems. An integer programming formulation and a new set of valid inequalities are presented for the linear characterization of the problem. A combination of a subgradient optimization procedure and an augmented Lagrangean-based procedure is used to generate tight lower bounds. The procedure begins with an explicit representation of a subset of the constraints, and the corresponding Lagrangean problem is solved. The solution is examined in order to identify implicit constraints that are violated. Those are added to the Lagrangean problem, forming an expanded problem, and an efficient dual ascent procedure is then applied. When no further improvement is possible through this procedure, a subgradient optimization procedure is invoked in order to further tighten the lower bound value. An exchange heuristic is applied to the nonfeasible Lagrangean solution, in an attempt to generate good feasible solutions to the problem. The procedure has been tested and has generated bounds that are significantly better than ones obtained through previously published procedures.     

Cramer-Rao bounds for parametric shape estimation in inverse problems

We address the problem of computing fundamental performance bounds for estimation of object boundaries from noisy measurements in inverse problems, when the boundaries are parameterized by a finite number of unknown variables. Our model applies to multiple unknown objects, each with its own unknown gray level, or color, and boundary parameterization, on an arbitrary known background. While such fundamental bounds on the performance of shape estimation algorithms can in principle be derived from the Cramer-Rao lower bounds, very few results have been reported due to the difficulty of computing the derivatives of a functional with respect to shape deformation. We provide a general formula for computing Cramer-Rao lower bounds in inverse problems where the observations are related to the object by a general linear transform, followed by a possibly nonlinear and noisy measurement system. As an illustration, we derive explicit formulas for computed tomography, Fourier imaging, and deconvolution problems. The bounds reveal that highly accurate parametric reconstructions are possible in these examples, using severely limited and noisy data.     

Estimation of constrained parameters in a linear model withmultiplicative and additive noise

Estimation of a Hilbert-space valued parameter in a linear model with compact linear transformation is considered with both multiplicative and additive noise present. The unknown parameter is assumed a priori to lie in a compact rectangular parallelepiped oriented in a certain way in the Hilbert space. Linear estimators are devised that minimize reasonable upper bounds on mean-squared error depending on conditions on the noise. Under prescribed conditions the estimators are minimax in the class of linear estimators. With the prior constraint on the unknown parameter removed, the estimation problem is ill-posed. Restricting the unknown provides a regularization of the basically ill-posed estimation. It turns out the estimators developed here belong to a well-known class of regularized estimators. With the interpretation that the constraint is soft, the procedure is applicable to many signal-processing problems     

The dual Pythagorean theorem and bad data detection

A new geometric interpretation of minimum variance estimation is presented in terms of the dual of the well-known Pythagorean theorem. The problem of bad data detection among redundant measurements is analyzed and simplified using relationships developed by the dual theorem.     

H∞ inferential filtering, prediction and smoothing problems

A new type of H_∞ optimal linear estimation problem is considered where no direct measurement of the output to be estimated is available. The optimal filter, predictor and smoother are derived for this case where outputs must be inferred from available measurements. The results cover the usual discrete time filtering problems and also optimal deconvolution estimation problems. They also apply to the situation, often found in industry, where estimates of signals are required which can only be determined from secondary measurements. An equalizing solution to the H_∞ problem is obtained, ensuring that the estimation error spectrum is determined directly by the choice of the dynamic cost-weighting function.     

Maximum likelihood and lower bounds in system identification withnon-Gaussian inputs

We consider the problem of estimating the parameters of an unknown discrete linear system driven by a sequence of independent identically distributed (i.i.d.) random variables whose probability density function (PDF) may be non-Gaussian. We assume a general system structure that may contain causal and noncausal poles and zeros. The parameters characterizing the input PDF may also be unknown. We derive an asymptotic expression for the Cramer-Rao lower bound, and show that it is the highest (worst) in the Gaussian case, indicating that the estimation accuracy can only be improved when the input PDF is non-Gaussian. It is further shown that the asymptotic error variance in estimating the system parameters is unaffected by lack of knowledge of the PDF parameters, and vice verse. Computationally efficient gradient-based algorithms for finding the maximum likelihood estimate of the unknown system and PDF parameters, which incorporate backward filtering for the identification of non-causal parameters, are presented. The dual problem of blind deconvolution/equalization is considered, and asymptotically attainable lower bounds on the equalization performance are derived. These bounds imply that it is preferable to work with compact equalizer structures characterized by a small number of parameters as the attainable performance depend only on the total number of equalizer parameters     

On the Probability of Undetected Error for Linear Block Codes

The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.     

Integer parameter estimation in linear models with applications toGPS

We consider parameter estimation in linear models when some of the parameters are known to be integers. Such problems arise, for example, in positioning using carrier phase measurements in the global positioning system (GPS), where the unknown integers enter the equations as the number of carrier signal cycles between the receiver and the satellites when the carrier signal is initially phase locked. Given a linear model, we address two problems: (1) the problem of estimating the parameters and (2) the problem of verifying the parameter estimates. We show that with additive Gaussian measurement noise the maximum likelihood estimates of the parameters are given by solving an integer least-squares problem. Theoretically, this problem is very difficult computationally (NP-hard); verifying the parameter estimates (computing the probability of estimating the integer parameters correctly) requires computing the integral of a Gaussian probability density function over the Voronoi cell of a lattice. This problem is also very difficult computationally. However, by using a polynomial-time algorithm due to Lenstra, Lenstra, and Lovasz (1982), the LLL algorithm, the integer least-squares problem associated with estimating the parameters can be solved efficiently in practice; sharp upper and lower bounds can be found on the probability of correct integer parameter estimation. We conclude the paper with simulation results that are based on a synthetic GPS setup     

Online SVR Training by Solving the Primal Optimization Problem

Online estimation of regression functions becomes important in presence of drifts and rapid changes in the training data. In this article we propose a new online training algorithm for SVR, called Priona, which is based on the idea of computing approximate solutions to the primal optimization problem. For the solution of the primal SVR problem we investigated the trade-off between computation time and prediction accuracy for the gradient, diagonally scaled gradient, and Newton descent direction. The choice of a particular buffering strategy did not influence the performance of the algorithm. By using a line search Priona does not require a priori selection of a learning rate which facilitates its practical application. On various benchmark data sets Priona is shown to perform better in terms of prediction accuracy in comparison to the Norma and Silk online SVR algorithms. Further, tests on two artificial data sets show that the online SVR algorithms are able to track temporal changes and drifts of the regression function, if the buffer size and learning rate are selected appropriately.     

FDD大规模MIMO系统速率最大化导频信号设计方法

该文针对FDD大规模MIMO下行系统,联合考虑信道空间相关性、信道估计精度和波束成型方案对导频信号设计的影响,以最大化下行遍历可达速率为目标,以系统总功耗为约束,建立关于导频信号矩阵的优化模型。由于原始优化问题的目标函数没有闭合形式表达式,利用大维矩阵理论中确定性等价原理可获得其近解析表达式,从而得到了遍历速率关于导频矩阵的显示表达式。基于此,利用主导理论,推导出了最优导频信号所具有的矩阵结构特征。进而,将原优化问题转换为等价的导频序列功率分配问题,再利用拉格朗日对偶法求解得到了最优导频信号的闭合形式解。通过分析,给出了最优导频序列长度的实际值与最大范围。数值仿真结果验证了所推导的遍历速率解析表达式的精确性和有效性,并对比了所提出的导频方案与传统基于最小均方误差准则导频方案在遍历速率方面的性能增益,以及所使用的导频序列长度差异,同时给出了两种方案在导频信号功率分配时的差异性。      

解线性及二次型规划问题增广的神经网络

本文提出了一个解线性及二次型规划问题的神经网络模型，证明了该网络是全局稳定于平衡点，而平衡点就是线性及二次型规划问题的解，该网络的优点是能够实时获得问题的精确解，且可以同时获得带等式不式约束的对偶问题解，该网络易于电路实现。     

H2 inferential filtering, prediction, and smoothing withapplication to rolling mill gauge estimation

A new minimum mean square error optimal linear estimation problem is considered where no direct measurement of the output to be estimated is available. The optimal filter, predictor, and smoother are derived for this case where outputs must be inferred from available measurements. The results cover the usual Wiener or Kalman filtering problems and also optimal deconvolution estimation problems. However, they also apply to the situation, often found in industry, where estimates of signals are required that can only be determined from secondary measurements. A weighted H₂ cost-function is minimized where the weighting function can be chosen to improve the robustness of the solution. The optimal estimators are derived both for stable and for unstable signal source models. A signal-processing application is considered in detail to demonstrate the use of the optimal filter. The gauge control problem in metal rolling mills is discussed where only force measurements are available     

Maximally Informative Feature and Sensor Selection in Pattern Recognition Using Local and Global Independent Component Analysis

In pattern recognition, a suitable criterion for feature selection is the mutual information (MI) between feature vectors and class labels. Estimating MI in high dimensional feature spaces is problematic in terms of computation load and accuracy. We propose an independent component analysis based MI estimation (ICA-MI) methodology for feature selection. This simplifies the high dimensional MI estimation problem into multiple one-dimensional MI estimation problems. Nonlinear ICA transformation is achieved using piecewise local linear approximation on partitions in the feature space, which allows the exploitation of the additivity property of entropy and the simplicity of linear ICA algorithms. Number of partitions controls the tradeoff between more accurate approximation of the nonlinear data topology and small-sample statistical variations in estimation. We test the ICA-MI feature selection framework on synthetic, UCI repository, and EEG activity classification problems. Experiments demonstrate, as expected, that the selection of the number of partitions for local linear ICA is highly problem dependent and must be carried out properly through cross validation. When this is done properly, the proposed ICA-MI feature selection framework yields feature ranking results that are comparable to the optimal probability of error based feature ranking and selection strategy at a much lower computational load.     

Solving inverse problems with piecewise linear estimators: from Gaussian mixture models to structured sparsity

A general framework for solving image inverse problems with piecewise linear estimations is introduced in this paper. The approach is based on Gaussian mixture models, which are estimated via a maximum a posteriori expectation-maximization algorithm. A dual mathematical interpretation of the proposed framework with a structured sparse estimation is described, which shows that the resulting piecewise linear estimate stabilizes the estimation when compared with traditional sparse inverse problem techniques. We demonstrate that, in a number of image inverse problems, including interpolation, zooming, and deblurring of narrow kernels, the same simple and computationally efficient algorithm yields results in the same ballpark as that of the state of the art.     

System parameter estimation with input/output noisy data andmissing measurements

An investigation is undertaken to examine the parameter estimation problem of linear systems when some of the measurements are unavailable (i.e., missing data) and the probability of occurrence of missing data is unknown a priori. The system input and output data are also assumed to be corrupted by measurement noise, and the knowledge of the noise distribution is unknown. Under the unknown noise distribution and missing measurements, a consistent parameter estimation algorithm [which is based on an l_p norm iterative estimation algorithm-iteratively reweighted least squares (IRLS)] is proposed to estimate the system parameters. We show that if the probability of missing measurement is less than one half, the parameter estimates via the proposed estimation algorithm will converge to the true parameters as the number of data tends to infinity. Finally, several simulation results are presented to illustrate the performance of the proposed l _p norm iterative estimation algorithm. Simulation results indicate that under input/output missing data and noise environment, the proposed parameter estimation algorithm is an efficient approach toward the system parameter estimation problem     

Mean likelihood frequency estimation

Estimation of signals with nonlinear as well as linear parameters in noise is studied. Maximum likelihood estimation has been shown to perform the best among all the methods. In such problems, joint maximum likelihood estimation of the unknown parameters reduces to a separable optimization problem, where first, the nonlinear parameters are estimated via a grid search, and then, the nonlinear parameter estimates are used to estimate the linear parameters. We show that a grid search can be avoided by using the mean likelihood estimator for estimating the unknown nonlinear parameters and how its performance can be made equivalent to that of the maximum likelihood estimator (MLE). The mean likelihood estimator requires computation of a multidimensional integral. However, using the concepts of importance sampling, we obtain the mean likelihood estimate without using integration. The technique is computationally far less burdensome than the direct maximum likelihood method but performs just as well. Simulation examples for estimating frequencies of multiple sinusoids in noise are given. The general technique can be applied to a large class of nonlinear regression problems