Independent component analysis (ICA) deals with the problem of estimating unknown latent variables (independent components) from observed data. One of the previous studies of ICA assumes a Laplace distribution on independent components. However, this assumption makes it difficult to calculate the posterior distribution of independent components. On the other hand, in the problem of sparse linear regression, several studies have approximately calculated the posterior distribution of parameters by assuming a hierarchical model expressing a Laplace distribution. This paper considers ICA in which a hierarchical model expressing a Laplace distribution is assumed on independent components. For this hierarchical model, we propose a method of calculating the approximate posterior distribution of independent components by using a variational Bayes method. Through some experiments, we show the effectiveness of our proposed method.

In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance d(fp) of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to. inverted left perpendiculard(fp)/2inverted right perpendicular - 1 errors.

In this paper, we develop a new decoding algorithm of binary linear codes for symbol-pair read channel. The Symbol-pair read channel has recently been introduced by Cassuto and Blaum to model channel whose write resolution is higher than read resolution. The proposed decoding algorithm is based on the linear programming (LP). It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance d(fp) of the code which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to [d(fp)/2] - 1 errors.

A new theory known as compressed sensing considers the problem to acquire and recover a sparse signal from its linear measurements. In this paper, we propose a new support recovery algorithm from noisy measurements based on the linear programming (LP). LP is widely used to estimate sparse signals, however, we focus on the problem to recover the support of sparse signals rather than the problem to estimate sparse signals themselves. First, we derive an integer linear programming (ILP) formulation for the support recovery problem. Then we obtain the LP based support recovery algorithm by relaxing the ILP. The proposed LP based recovery algorithm has an attracting property that the output of the algorithm is guaranteed to be the maximum a posteiori (MAP) estimate when it is integer valued. We compare the performance of the proposed algorithm to a state-of-the-art algorithm named sparse matching pursuit (SMP) via numerical simulations.

The electronic commerce site (EC site) has become an important marketing channel where consumers can purchase many kinds of products
their access logs, including purchase records and browsing histories, are saved in the EC sites' databases. These log data can be utilized for the purpose of web marketing. The customers who purchase many product items are good customers, whereas the other customers, who do not purchase many items, must not be good customers even if they browse many items. If the attributes of good customers and those of other customers are clarified, such information is valuable as input for making a new marketing strategy. Regarding the product items, the characteristics of good items that are bought by many users are valuable information. It is necessary to construct a method to efficiently analyze such characteristics. This paper proposes a new latent class model to analyze both purchasing and browsing histories to make latent item and user clusters. By applying the proposal, an example of data analysis on an EC site is demonstrated. Through the clusters obtained by the proposed latent class model and the classification rule by the decision tree model, new findings are extracted from the data of purchasing and browsing histories.

In this paper, we study a privacy preserving linear regression analysis. We propose a new protocol of a distributed calculation method that calculates a least squares estimator, in the case that two parties have different types of explanatory variables. We show the security of privacy in the proposed protocol. Because the protocol have iterative calculations, we evaluate the number of iterations via numerical experiments. Finally, we show an extended protocol that is a distributed calculation method for k parties.

In this paper, we consider a completion problem of multiple related matrices. Matrix completion problem is the problem to estimate unobserved elements of the matrix from observed elements. It has many applications such as collaborative filtering, computer vision, biology, and so on. In cases where we can obtain some related matrices, we can expect that their simultaneous completion has better performance than completing each matrix independently. Collective matrix factorization is a powerful approach to jointly factorize multiple matrices. However, existing completion algorithms for the collective matrix factorization have some drawbacks. One is that most existing algorithms are based on non-convex formulations of the problem. Another is that only a few existing algorithms consider the strength of the relation among matrices and it results in worse performance when some matrices are actually not related. In this paper, we formulate the multiple matrix completion problem as the convex optimization problem. Moreover, it considers the strength of the relation among matrices. We also develop an optimization algorithm which solves the proposed problem efficiently based on the alternating direction method of multipliers (ADMM). We verify the effectiveness of our approach through numerical experiments on both synthetic data and real data set: MovieLens.

In this paper, we consider a completion problem of multiple related matrices. Matrix completion problem is the problem to estimate unobserved elements of the matrix from observed elements. It has many applications such as collaborative filtering, computer vision, biology, and so on. In cases where we can obtain some related matrices, we can expect that their simultaneous completion has better performance than completing each matrix independently. Collective matrix factorization is a powerful approach to jointly factorize multiple matrices. However, existing completion algorithms for the collective matrix factorization have some drawbacks. One is that most existing algorithms are based on non-convex formulations of the problem. Another is that only a few existing algorithms consider the strength of the relation among matrices and it results in worse performance when some matrices are actually not related. In this paper, we formulate the multiple matrix completion problem as the convex optimization problem. Moreover, it considers the strength of the relation among matrices. We also develop an optimization algorithm which solves the proposed problem efficiently based on the alternating direction method of multipliers (ADMM). We verify the effectiveness of our approach through numerical experiments on both synthetic data and real data set: MovieLens.

In this paper, we develop an iterative multiuser joint decoding of code-division multiple-access (CDMA) signals based on a distributed optimization algorithm. For the joint decoding problem, decoding algorithm based on the turbo principle is widely used. The algorithm consists of soft-input soft-output (SISO) channel decoder and SISO multiuser detector and it can be derived as an application of the sum-product algorithm. On the other hand, in the research area of error correcting codes, the decoding algorithm based on convex optimization has been attracting a great deal of attention. Decoding algorithm based on linear programming (LP) has decoding error rate which is comparable with sum-product algorithm with stronger theoretical guarantees. We formulate the joint decoding problem of CDMA signals as an convex optimization problem and we present a relax form of the problem. Moreover, we propose a distributed algorithm which efficiently solves the relaxed optimization problem. The proposed algorithm is based on alternating direction method of multipliers (ADMM). We also see the performance of the proposed decoder through numerical simulations. © 2013 IEEE.

In this paper, we develop an iterative multiuser joint decoding of code-division multiple-access (CDMA) signals based on a distributed optimization algorithm. For the joint decoding problem, decoding algorithm based on the turbo principle is widely used. The algorithm consists of soft-input soft-output (SISO) channel decoder and SISO multiuser detector and it can be derived as an application of the sum-product algorithm. On the other hand, in the research area of error correcting codes, the decoding algorithm based on convex optimization has been attracting a great deal of attention. Decoding algorithm based on linear programming (LP) has decoding error rate which is comparable with sum-product algorithm with stronger theoretical guarantees. We formulate the joint decoding problem of CDMA signals as an convex optimization problem and we present a relax form of the problem. Moreover, we propose a distributed algorithm which efficiently solves the relaxed optimization problem. The proposed algorithm is based on alternating direction method of multipliers (ADMM). We also see the performance of the proposed decoder through numerical simulations. © 2013 IEEE.

In this paper, we study a privacy preserving linear regression analysis. We propose a new protocol of distributed calculation method that calculates a least squares estimator, in case that two parties have different types of explanatory variables. We show security of privacy in the proposed protocol. Because the protocol have iterative calculation, we evaluate the number of iterations with numerical experiments. Finally, we show an extended protocol that is a distributed calculation method for κ parties.

In this paper, we develop a dual decomposition method based linear-programming (LP) decoding for multiple-access channels with binary linear codes. LP decoding has decoding error rate which is comparable with state-of-the-art Sum-Product decoder for the decoding problem of binary linear codes with stronger theoretical guarantees and it is applied to decoding problems over various channels such as interference channels and multiple-access channels. But the decoder has to solve an LP problem and in general its computational complexity is the polynomial order of the number of variables and the number of constraints. Therefore it needs more decoding time compared to other decoders such as Sum-Product decoder. In order to tackle the complexity problem, many complexity efficient decoders have been developed for single-user memoryless channels. Especially, some previous studies showed that the decoding algorithm based on dual decomposition works well for large scale LDPC codes. In this paper, we apply the dual decomposition methods for the decoding problem over multiple access channels.

We propose new algorithms for fault diagnosis problem based on the dual decomposition method and the augmented Lagrangian method. Our algorithms are convergent and those outputs are same as that of Linear Programming (LP) based fault diagnosis algorithm. The proposed algorithms have smaller computational complexity than ordinary LP solver. Experimental results show the practical potentials of the proposed algorithms.

A stream cipher is an important class of encryption algorithms. Its safety depends on the structure of the pseudo-random number generator used. There are various types of pseudo-random number generators in existence, and attack algorithms used on them have been studied individually. In this paper, we express the problem of attacks on a general stream cipher as a probabilistic inference problem, and formulate the optimal key estimation. We also propose a unified framework of attack algorithms that can be applied to a wide variety of stream ciphers. The optimal key estimation, however, has computational complexity. To reduce the complexity, an approximation algorithm based on a probabilistic inference is proposed. We also describe some attack algorithms used on practical pseudo-random number generators. Finally, the proposed algorithm is evaluated by through a computer simulation.

We propose new algorithms for fault diagnosis problem based on the dual decomposition method and the augmented Lagrangian method. Our algorithms are convergent and those outputs are same as that of Linear Programming (LP) based fault diagnosis algorithm. The proposed algorithms have smaller computational complexity than ordinary LP solver. Experimental results show the practical potentials of the proposed algorithms.

A stream cipher is an important class of encryption algorithms. Its safety depends on the structure of the pseudo-random number generator used. There are various types of pseudo-random number generators in existence, and attack algorithms used on them have been studied individually. In this paper, we express the problem of attacks on a general stream cipher as a probabilistic inference problem, and formulate the optimal key estimation. We also propose a unified framework of attack algorithms that can be applied to a wide variety of stream ciphers. The optimal key estimation, however, has computational complexity. To reduce the complexity, an approximation algorithm based on a probabilistic inference is proposed. We also describe some attack algorithms used on practical pseudo-random number generators. Finally, the proposed algorithm is evaluated by through a computer simulation.

Nowadays, it is pointed out that storing the secret in nonvolatile memory of the device has a chance to leak the secret because of physical attacks and side channel attacks. In order to solve this, Physical Unclonable Functions(PUF) were proposed. Recently, many encryption methods using PUF have been proposed, and one of typical example is authentication. In this paper, we define response to challenge of PUF as probability distribution, and we define error rate of authentication and success rate of impersonation attack by interpreting authentication using PUF as hypothesis testing problem. In authentication using PUP, we derive lower bound of success rate of impersonation attack when error rate of authentication is 0. And we define arbiter PUF which is one of silicon PUFs as probability distribution. In arbiter PUP, we simulate lower bound of success rate of the impersonation attack when error rate of authentication is 0, and discuss security of arbiter PUF.

The stream cipher which is a kind of symmetric key algorithm, is a cryptosystem to generate ciphertext by XOR plaintext bits and keystream bits which obtained by input a secret key to pseudorandom number generator. In this paper, we formularize the problem of the attack to stream cipher by statisitical decision theory, and consider the optimal key estimation based on Bayesian criterion. We represent practical pseudorandom number generator as a probabilistic model, and propose the key estimation algorithm based on probabilistic inference one by representing it to graphical model. The proposed algorithm is evaluated by simulation, then consider the safety of the stream cipher.

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a nonlinear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm. Copyright © 2011 The Institute of Electronics, Information and Communication Engineers.

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

Probabilisitc inference problem on the graphical model is very important since it is arising in many applications which include theory of error-correcting codes, image processing, speech recognition, and so on. Recently, linear programming based decoding algorithm for the error-correcting code has been receiving a lot of attention. Viewing the decoding problem as an example of the probabilistic inference problem on the graphical model, the factor graph corresponds to the problem has some specific structure. The functions in the factor graph can be classified into two classes, indicator functions and non-indicator functions. For the graph corresponds to the decoding problem, each non-indicator function is connected to only one variable node. On the other hand, the factor graph corresponds to the general probabilistic inference problems possibly have non-indicator functions which is connected to more than one variable nodes. The aim of this study is to develop the linear programming based inference algorithm for general inference problems.

Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP) Since it is an NP hard problem in general there are many researches about the algorithms to approximately solve the problem One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al LP decoding is based on the LP relaxation which Is a method to approximately solve the ILP corresponding to the ML decoding problem Advanced algorithms for solving ILP (approximately or exactly) include cutting plane method and branch and bound method As applications of these methods adaptive LP decoding and branch and bound decoding have been proposed by Taghavi et al and Yang et al respectively Another method for solving ILP is the branch and cut method which is a hybrid of cutting plane and branch and bound methods The branch and cut method is widely used to solve ILP however it is unobvious that the method works well for the ML decoding problem In this paper we show that the branch and cut method is certainly effective for the ML decoding problem Furthermore the branch and cut method consists of some technical components and the performance of the algorithm depends on the selection of these components It is important to consider how to select the technical components in the branch and cut method We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations

Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP) Since it is an NP hard problem in general there are many researches about the algorithms to approximately solve the problem One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al LP decoding is based on the LP relaxation which Is a method to approximately solve the ILP corresponding to the ML decoding problem Advanced algorithms for solving ILP (approximately or exactly) include cutting plane method and branch and bound method As applications of these methods adaptive LP decoding and branch and bound decoding have been proposed by Taghavi et al and Yang et al respectively Another method for solving ILP is the branch and cut method which is a hybrid of cutting plane and branch and bound methods The branch and cut method is widely used to solve ILP however it is unobvious that the method works well for the ML decoding problem In this paper we show that the branch and cut method is certainly effective for the ML decoding problem Furthermore the branch and cut method consists of some technical components and the performance of the algorithm depends on the selection of these components It is important to consider how to select the technical components in the branch and cut method We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations

In this paper, we develop a linear-programming (LP) decoding for the multiple-access channel with binary linear codes. For the single-user channel, LP decoding has been attracting much attention in recent years as a good approximation to the maximum likelihood decoding. We demonstrate that how the maximum likelihood decoding problem for the multiple-access channel with binary linear codes can be formulated as a linear programming problem. It is not straightforward because the objective function of the problem is a non-linear function of the codeword symbols in general. We introduce the auxiliary variables such that the objective function is a linear function of those variables. Then the ML decoding problem reduces to the LP problem however, it is too complex for practical implementation. As the case for the single-user channel, we formulate the relaxed LP problem. Just as in the case of the single-user channel, the proposed decoder has the desirable property called ML certificate property, that is, if the decoder outputs integer solution, it is guaranteed to be the ML codeword. The computational complexity of the proposed algorithm is the exponential order of the number of users, however, we can reduce the computational complexity of the algorithm for the gaussian multiple-access channel. Furthermore, we compare the performance of the proposed decoder with the decoder based on the sum-product algorithm.

Optimum detection for the multiuser code-division multiple-access channel is prohibitively complex. This paper considers new iterative multiuser detection algorithm based on the belief propagation algorithm. Previously, the idea to apply the belief propagation algorithm to multiuser detection problem was suggested , however, it was believed that to apply the belief propagation algorithm to the detection problem is impossible because it requires an exponentially large amount of computation. It was the only fact that the parallel interference canceller is derived as an approximation of the belief propagation. In this paper, we show that the belief propagation algorithm can be applied to the detection problem by converting the factor graph structure. Performance of the detector based on the belief propagation algorithm is better than that of the parallel interference canceller. © 2008 IEEE.