14 results
Search Results
2. Column-Wise Element Selection for Computationally Efficient Nonnegative Coupled Matrix Tensor Factorization.
- Author
-
Balasubramaniam, Thirunavukarasu, Nayak, Richi, Yuen, Chau, and Tian, Yu-Chu
- Subjects
- *
NONNEGATIVE matrices , *MATRIX decomposition , *ALGORITHMS , *LINEAR programming , *RECOMMENDER systems - Abstract
Coupled Matrix Tensor Factorization (CMTF) facilitates the integration and analysis of multiple data sources and helps discover meaningful information. Nonnegative CMTF (N-CMTF) has been employed in many applications for identifying latent patterns, prediction, and recommendation. However, due to the added complexity with coupling between tensor and matrix data, existing N-CMTF algorithms exhibit poor computation efficiency. In this paper, a computationally efficient N-CMTF factorization algorithm is presented based on the column-wise element selection, preventing frequent gradient updates. Theoretical and empirical analyses show that the proposed N-CMTF factorization algorithm is not only more accurate but also more computationally efficient than existing algorithms in approximating the tensor as well as in identifying the underlying nature of factors. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
3. ADMM Check Node Penalized Decoders for LDPC Codes.
- Author
-
Wei, Haoyuan and Banihashemi, Amir H.
- Subjects
- *
MONTE Carlo method , *ALGORITHMS , *LINEAR programming , *SIGNAL-to-noise ratio , *ERROR rates , *LOW density parity check codes , *DECODING algorithms - Abstract
Alternating direction method of multipliers (ADMM) is an efficient implementation of linear programming (LP) decoding for low-density parity-check (LDPC) codes. By adding penalty terms to the objective function of the LP decoding model, ADMM variable node (VN) penalized decoding can suppress the non-integral solutions and improve the frame error rate (FER) performance in the low signal-to-noise ratio (SNR) region. In this paper, we propose a novel ADMM check node (CN) penalized decoding algorithm. Codeword solutions which satisfy all parity-check equations will have smaller penalty values than non-codeword solutions, including the non-integral solutions. We discuss the required properties of CN-penalty functions, propose a few functions that satisfy those properties, and study their performance/complexity trade-offs. We also investigate the convergence properties of the proposed algorithm and prove that its performance is independent of the transmitted codeword. Using Monte Carlo simulations and instanton analysis, we then demonstrate that the proposed CN-penalized decoder outperforms ADMM VN penalized decoders in both waterfall and error floor regions. This comes at the expense of some increase in the decoding complexity. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
4. Distributed Resource Allocation Over Directed Graphs via Continuous-Time Algorithms.
- Author
-
Zhu, Yanan, Ren, Wei, Yu, Wenwu, and Wen, Guanghui
- Subjects
- *
RESOURCE allocation , *CONVEX sets , *ALGORITHMS , *SWARM intelligence , *CONVEX functions , *LINEAR programming , *DIRECTED graphs - Abstract
This paper investigates the resource allocation problem for a group of agents communicating over a strongly connected directed graph, where the total objective function of the problem is composted of the sum of the local objective functions incurred by the agents. With local convex sets, we first design a continuous-time projection algorithm over a strongly connected and weight-balanced directed graph. Our convergence analysis indicates that when the local objective functions are strongly convex, the output state of the projection algorithm could asymptotically converge to the optimal solution of the resource allocation problem. In particular, when the projection operation is not involved, we show the exponential convergence at the equilibrium point of the algorithm. Second, we propose an adaptive continuous-time gradient algorithm over a strongly connected and weight-unbalanced directed graph for the reduced case without local convex sets. In this case, we prove that the adaptive algorithm converges exponentially to the optimal solution of the considered problem, where the local objective functions and their gradients satisfy strong convexity and Lipachitz conditions, respectively. Numerical simulations illustrate the performance of our algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. The Estimation Performance of Nonlinear Least Squares for Phase Retrieval.
- Author
-
Huang, Meng and Xu, Zhiqiang
- Subjects
- *
NONLINEAR estimation , *ALACHLOR , *ALGORITHMS , *RANDOM matrices , *RANDOM variables - Abstract
Suppose that ${ { y}}= \lvert \text {A} { x}_{0}\rvert +\eta $ where ${ x}_{0}\in {\mathbb R} ^{{d}}$ is the target signal and $\eta \in {\mathbb R}^{{m}}$ is a noise vector. The aim of phase retrieval is to estimate ${x}_{0}$ from ${ { y}}$. A popular model for estimating ${ x}_{0}$ is the nonlinear least squares ${\widehat { {x}}}:={\mathrm{ argmin}}_{ x} \| \lvert \text {A} { x}\rvert - { { y}}\|_{2}$. One has already developed many efficient algorithms for solving the model, such as the seminal error reduction algorithm. In this paper, we present the estimation performance of the model with proving that $\| {\widehat { {x}}}- { x}_{0}\|\lesssim {\|\eta \|_{2}}/{\sqrt {{m}}}$ under the assumption of A being a Gaussian random matrix. We also prove the reconstruction error ${\|\eta \|_{2}}/{\sqrt {{m}}}$ is sharp. For the case where ${ x}_{0}$ is sparse, we study the estimation performance of both the nonlinear Lasso of phase retrieval and its unconstrained version. Our results are non-asymptotic, and we do not assume any distribution on the noise $\eta $. To the best of our knowledge, our results represent the first theoretical guarantee for the nonlinear least squares and for the nonlinear Lasso of phase retrieval. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
6. $\alpha$-Fair Power Allocation in Spectrum-Sharing Networks.
- Author
-
Guo, Chongtao, Zhang, Yan, Sheng, Min, Wang, Xijun, and Li, Yuzhou
- Subjects
- *
TELECOMMUNICATION spectrum , *SPECTRUM allocation , *CHANNEL spacing (Telecommunication) , *COGNITIVE radio , *ALGORITHMS - Abstract
To efficiently trade off system sum-rate and link fairness, this paper is dedicated to maximizing the sum of \alpha-fair utility in spectrum-sharing networks, where multiple interfering links share one channel. In the literature, three special cases, including \alpha=\mbox{0} (sum-rate maximization), \alpha=\mbox{1} (proportional fairness), and \alpha=\infty (max-min fairness), have been investigated; the complexity for cases \mbox{1} < \alpha < \infty and \mbox{0} < \alpha < \mbox{1} is still unknown. In this paper, we prove that the problem is convex when \mbox1 < \alpha < \infty and is NP-hard when \mbox0 < \alpha < \mbox1. To deal with the latter case, we transform the objective function and represent it by the difference of two concave functions (D.C.). Then, a power allocation algorithm is proposed with fast convergence to a local optimal point. Simulation results show that the proposed algorithm can obtain global optimality in two-link cases when \mbox0 < \alpha < \mbox1. In addition, we can get a flexible tradeoff between sum-rate and fairness in terms of Jain's index by adjusting $\alpha$. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
7. A Proximal Gradient Algorithm for Decentralized Composite Optimization.
- Author
-
Shi, Wei, Ling, Qing, Wu, Gang, and Yin, Wotao
- Subjects
- *
ALGORITHMS , *DIGITAL signal processing , *NONSMOOTH optimization , *QUADRATIC programming , *COMPRESSED sensing - Abstract
This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a static networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized constrained quadratic programming and compressed sensing problems, as well as many regularization problems arising in inverse problems, signal processing, and machine learning, which have decentralized applications. This paper addresses the need for efficient decentralized algorithms that take advantages of proximal operations for the nonsmooth terms. We propose a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the composite structure and has the best known convergence rate. It is a nontrivial extension to the recent algorithm EXTRA. At each iteration, each agent locally computes a gradient of the smooth part of its objective and a proximal map of the nonsmooth part, as well as exchanges information with its neighbors. The algorithm is “exact” in the sense that an exact consensus minimizer can be obtained with a fixed step size, whereas most previous methods must use diminishing step sizes. When the smooth part has Lipschitz gradients, PG-EXTRA has an ergodic convergence rate of O\left(1\over k\right) in terms of the first-order optimality residual. When the smooth part vanishes, PG-EXTRA reduces to P-EXTRA, an algorithm without the gradients (so no “G” in the name), which has a slightly improved convergence rate at o\left(1\over k\right) in a standard (non-ergodic) sense. Numerical experiments demonstrate effectiveness of PG-EXTRA and validate our convergence results [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
8. Optimizing Leader Influence in Networks Through Selection of Direct Followers.
- Author
-
Mai, Van Sy and Abed, Eyad H.
- Subjects
- *
GREEDY algorithms , *MATHEMATICAL optimization , *MATHEMATICAL models , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
This paper considers the problem of a leader that seeks to optimally influence the opinions of agents in a directed network through connecting with a limited number of the agents (“direct followers”), possibly in the presence of a fixed competing leader. The settings involving a single leader and two competing leaders are unified into a general combinatoric optimization problem, for which two heuristic approaches are developed. The first approach is based on a convex relaxation scheme, possibly in combination with the $\ell _1$ -norm regularization technique, and the second is based on a greedy selection strategy. The main technical novelties of this work are in the establishment of supermodularity of the objective function and convexity of its continuous relaxation. The greedy approach is guaranteed to have a lower bound on the approximation ratio sharper than $(1-1/e)$ , while the convex approach can benefit from efficient (customized) numerical solvers to have practically comparable solutions possibly with faster computation times. The two approaches can be combined to provide improved results. In numerical examples, the approximation ratio can be made to reach ${\text{90}\%}$ or higher depending on the number of direct followers. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. Sparse Learning with Stochastic Composite Optimization.
- Author
-
Zhang, Weizhong, Zhang, Lijun, Jin, Zhongming, Jin, Rong, Cai, Deng, Li, Xuelong, Liang, Ronghua, and He, Xiaofei
- Subjects
- *
EDUCATION , *MATHEMATICAL programming , *ALGORITHMS , *MATHEMATICAL optimization , *FIBERS - Abstract
In this paper, we study Stochastic Composite Optimization (SCO) for sparse learning that aims to learn a sparse solution from a composite function. Most of the recent SCO algorithms have already reached the optimal expected convergence rate \mathcal O(1/\lambda T)
with $\delta$- Published
- 2017
- Full Text
- View/download PDF
10. Complexity Certification of a Distributed Augmented Lagrangian Method.
- Author
-
Lee, Soomin, Chatzipanagiotis, Nikolaos, and Zavlanos, Michael M.
- Subjects
- *
LAGRANGE equations , *ALGORITHMS , *COMPUTATIONAL complexity , *PREDICTIVE control systems , *CONVEX domains , *MATHEMATICAL models - Abstract
In this paper, we present complexity certification results for a distributed augmented Lagrangian (AL) algorithm used to solve convex optimization problems involving globally coupled linear constraints. Our method relies on the accelerated distributed AL (ADAL) algorithm, which can handle the coupled linear constraints in a distributed manner based on local estimates of the AL. We show that the theoretical complexity of ADAL to reach an $\epsilon$-optimal solution both in terms of suboptimality and infeasibility is O(\frac{1}{\epsilon }) iterations. Moreover, we provide a valid upper bound for the optimal dual multiplier, which enables us to explicitly specify these complexity bounds. We also show how to choose the step-size parameter to minimize the bounds on the convergence rates. Finally, we discuss a motivating example, a model predictive control problem, involving a finite number of subsystems, which interact with each other via a general network. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
11. Decomposition Techniques for Multilayer Perceptron Training.
- Author
-
Grippo, Luigi, Manno, Andrea, and Sciandrone, Marco
- Subjects
- *
CHEMICAL decomposition , *ARTIFICIAL neural networks , *MULTILAYER perceptrons , *ALGORITHMS , *COMPUTATIONAL learning theory , *EDUCATION - Abstract
In this paper, we consider the learning problem of multilayer perceptrons (MLPs) formulated as the problem of minimizing a smooth error function. As well known, the learning problem of MLPs can be a difficult nonlinear nonconvex optimization problem. Typical difficulties can be the presence of extensive flat regions and steep sided valleys in the error surface, and the possible large number of training data and of free network parameters. We define a wide class of batch learning algorithms for MLP, based on the use of block decomposition techniques in the minimization of the error function. The learning problem is decomposed into a sequence of smaller and structured minimization problems in order to advantageously exploit the structure of the objective function. Theoretical convergence results are established, and a specific algorithm is constructed and evaluated through an extensive numerical experimentation. The comparisons with the state-of-the-art learning algorithms show the effectiveness of the proposed techniques. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
12. Constrained Clustering With Nonnegative Matrix Factorization.
- Author
-
Zhang, Xianchao, Zong, Linlin, Liu, Xinyue, and Luo, Jiebo
- Subjects
- *
DOCUMENT clustering , *ALGORITHMS , *SYMMETRIC matrices , *DATA mining , *MACHINE learning , *MATHEMATICAL models - Abstract
Nonnegative matrix factorization (NMF) and symmetric NMF (SymNMF) have been shown to be effective for clustering linearly separable data and nonlinearly separable data, respectively. Nevertheless, many practical applications demand constrained algorithms in which a small number of constraints in the form of must-link and cannot-link are available. In this paper, we propose an NMF-based constrained clustering framework in which the similarity between two points on a must-link is enforced to approximate 1 and the similarity between two points on a cannot-link is enforced to approximate 0. We then formulate the framework using NMF and SymNMF to deal with clustering of linearly separable data and nonlinearly separable data, respectively. Furthermore, we present multiplicative update rules to solve them and show the correctness and convergence. Experimental results on various text data sets, University of California, Irvine (UCI) data sets, and gene expression data sets demonstrate the superiority of our algorithms over existing constrained clustering algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
13. Compound Rank- $k$ Projections for Bilinear Analysis.
- Author
-
Chang, Xiaojun, Nie, Feiping, Wang, Sen, Yang, Yi, Zhou, Xiaofang, and Zhang, Chengqi
- Subjects
- *
DISCRIMINANT analysis , *FEATURE extraction , *BILINEAR transformation method , *ALGORITHMS , *ARTIFICIAL neural networks - Abstract
In many real-world applications, data are represented by matrices or high-order tensors. Despite the promising performance, the existing 2-D discriminant analysis algorithms employ a single projection model to exploit the discriminant information for projection, making the model less flexible. In this paper, we propose a novel compound rank- $k$ projection (CRP) algorithm for bilinear analysis. The CRP deals with matrices directly without transforming them into vectors, and it, therefore, preserves the correlations within the matrix and decreases the computation complexity. Different from the existing 2-D discriminant analysis algorithms, objective function values of CRP increase monotonically. In addition, the CRP utilizes multiple rank- $k$ projection models to enable a larger search space in which the optimal solution can be found. In this way, the discriminant ability is enhanced. We have tested our approach on five data sets, including UUIm, CVL, Pointing’04, USPS, and Coil20. Experimental results show that the performance of our proposed CRP performs better than other algorithms in terms of classification accuracy. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
14. A Fast Algorithm for Nonnegative Matrix Factorization and Its Convergence.
- Author
-
Li, Li-Xin, Wu, Lin, Zhang, Hui-Sheng, and Wu, Fang-Xiang
- Subjects
- *
ALGORITHMS , *FACTORIZATION , *STOCHASTIC convergence , *MATHEMATICAL functions , *MATHEMATICAL optimization , *DIVERGENCE theorem - Abstract
Nonnegative matrix factorization (NMF) has recently become a very popular unsupervised learning method because of its representational properties of factors and simple multiplicative update algorithms for solving the NMF. However, for the common NMF approach of minimizing the Euclidean distance between approximate and true values, the convergence of multiplicative update algorithms has not been well resolved. This paper first discusses the convergence of existing multiplicative update algorithms. We then propose a new multiplicative update algorithm for minimizing the Euclidean distance between approximate and true values. Based on the optimization principle and the auxiliary function method, we prove that our new algorithm not only converges to a stationary point, but also does faster than existing ones. To verify our theoretical results, the experiments on three data sets have been conducted by comparing our proposed algorithm with other existing methods. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.