The Experts below are selected from a list of 16116 Experts worldwide ranked by ideXlab platform

Somenath Biswas - One of the best experts on this subject based on the ideXlab platform.

  • Efficacy of the Metropolis Algorithm for the Minimum-Weight Codeword Problem Using Codeword and Generator Search Spaces
    IEEE Transactions on Evolutionary Computation, 2020
    Co-Authors: K. B. Ajitha Shenoy, Somenath Biswas, Piyush P. Kurur
    Abstract:

    This article studies the efficacy of the Metropolis Algorithm for the minimum-weight codeword problem . The input is a linear code $C$ given by its generator matrix and our task is to compute a nonzero codeword in the code $C$ of least weight. In particular, we study the Metropolis Algorithm on two possible search spaces for the problem: 1) the codeword space and 2) the generator space . The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this article. In this article, we show that for an appropriately chosen temperature parameter the Metropolis Algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis Algorithm performs favorably when compared to previous attempts. When using the generator space, the Metropolis Algorithm is able to outperform the previous Algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem.

  • GECCO - Performance of Metropolis Algorithm for the minimum weight code word problem
    Proceedings of the 2014 conference on Genetic and evolutionary computation - GECCO '14, 2014
    Co-Authors: Ajitha Shenoy K. B, Somenath Biswas, Piyush P. Kurur
    Abstract:

    We study the performance of the Metropolis Algorithm for the problem of finding a code word of weight less than or equal to M, given a generator matrix of an [n,k]-binary linear code. The Algorithm uses the set Sk of all kxk invertible matrices as its search space where two elements are considered adjacent if one can be obtained from the other via an elementary row operation (i.e by adding one row to another or by swapping two rows.) We prove that the Markov chains associated with the Metropolis Algorithm mix rapidly for suitable choices of the temperature parameter T. We ran the Metropolis Algorithm for a number of codes and found that the Algorithm performed very well in comparison to previously known experimental results.

  • Search Graph Formulation and Hasting's Generalization of Metropolis Algorithm For Solving SVP
    2013
    Co-Authors: K. B. Ajitha Shenoy, Somenath Biswas, Piyush P. Kurur
    Abstract:

    Shortest Lattice Vector Problem (SVP) has numer- ous applications spanning from robotics to computational num- ber theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the prob- lem that runs in polynomial time. What one normally uses is the LLL Algorithm which, although a polynomial time Algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Hasting's generalization of the Metropolis Algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We also proved that our search space graphs for SVP has mag- nification greater than half. We have implemented the Metropo- lis Algorithm and Hasting's generalization of the Metropolis al- gorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL Algorithm.

  • Effect of increasing the energy gap between the two lowest energy states on the mixing time of the Metropolis Algorithm
    Information Processing Letters, 2012
    Co-Authors: Apurv Nakade, Somenath Biswas
    Abstract:

    In order to understand what makes natural proteins fold rapidly, Sali, Shakhnovich and Karplus (1994) [6,7] had used the Metropolis Algorithm to search for the minimum energy conformations of chains of beads in the lattice model of protein folding. Based on their computational experiments, they concluded that the Metropolis Algorithm would find the minimum energy conformation of a chain of beads within an acceptable time scale if and only if there is a large gap between the energies of the minimum energy conformation and that of the second minimum. Clote (1999) [1] attempted to support this conclusion by a proof that the mixing time of the underlying Markov chain would decrease as the gap in energies of the minimum energy conformation and that of the second minimum increased. He was able to show that an upper bound on the mixing time does indeed decrease as the energy gap increases. We show in this paper that the mixing time itself, however, is a non-decreasing function of the value of the energy gap. Therefore, our result contradicts what Clote had attempted to prove.

  • Metropolis Algorithm for solving shortest lattice vector problem svp
    International Conference Hybrid Intelligent Systems, 2011
    Co-Authors: Shenoy K B Ajitha, Somenath Biswas, Piyush P. Kurur
    Abstract:

    In this paper we study the suitability of the Metropolis Algorithm and its generalization for solving the shortest lattice vector problem (SVP). SVP has numerous applications spanning from robotics to computational number theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the problem that runs in polynomial time. What one normally uses is the LLL Algorithm which, although a polynomial time Algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Metropolis Algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We can use this search space formulation for some other classes of evolutionary Algorithms, e.g., for genetic and go-with-the-winner Algorithms. We have implemented the Metropolis Algorithm and Hasting's generalization of Metropolis Algorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL Algorithm.

Alain Aspuruguzik - One of the best experts on this subject based on the ideXlab platform.

  • a quantum quantum Metropolis Algorithm
    Proceedings of the National Academy of Sciences of the United States of America, 2012
    Co-Authors: Man-hong Yung, Alain Aspuruguzik
    Abstract:

    The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum Algorithm which fully generalizes the classical Metropolis Algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed Algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum Algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this Algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.

Man-hong Yung - One of the best experts on this subject based on the ideXlab platform.

  • a quantum quantum Metropolis Algorithm
    Proceedings of the National Academy of Sciences of the United States of America, 2012
    Co-Authors: Man-hong Yung, Alain Aspuruguzik
    Abstract:

    The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum Algorithm which fully generalizes the classical Metropolis Algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed Algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum Algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this Algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.

  • A quantum–quantum Metropolis Algorithm
    Proceedings of the National Academy of Sciences, 2012
    Co-Authors: Man-hong Yung, Alán Aspuru-guzik
    Abstract:

    The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum Algorithm which fully generalizes the classical Metropolis Algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed Algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum Algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this Algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.

Piyush P. Kurur - One of the best experts on this subject based on the ideXlab platform.

  • Efficacy of the Metropolis Algorithm for the Minimum-Weight Codeword Problem Using Codeword and Generator Search Spaces
    IEEE Transactions on Evolutionary Computation, 2020
    Co-Authors: K. B. Ajitha Shenoy, Somenath Biswas, Piyush P. Kurur
    Abstract:

    This article studies the efficacy of the Metropolis Algorithm for the minimum-weight codeword problem . The input is a linear code $C$ given by its generator matrix and our task is to compute a nonzero codeword in the code $C$ of least weight. In particular, we study the Metropolis Algorithm on two possible search spaces for the problem: 1) the codeword space and 2) the generator space . The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this article. In this article, we show that for an appropriately chosen temperature parameter the Metropolis Algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis Algorithm performs favorably when compared to previous attempts. When using the generator space, the Metropolis Algorithm is able to outperform the previous Algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem.

  • GECCO - Performance of Metropolis Algorithm for the minimum weight code word problem
    Proceedings of the 2014 conference on Genetic and evolutionary computation - GECCO '14, 2014
    Co-Authors: Ajitha Shenoy K. B, Somenath Biswas, Piyush P. Kurur
    Abstract:

    We study the performance of the Metropolis Algorithm for the problem of finding a code word of weight less than or equal to M, given a generator matrix of an [n,k]-binary linear code. The Algorithm uses the set Sk of all kxk invertible matrices as its search space where two elements are considered adjacent if one can be obtained from the other via an elementary row operation (i.e by adding one row to another or by swapping two rows.) We prove that the Markov chains associated with the Metropolis Algorithm mix rapidly for suitable choices of the temperature parameter T. We ran the Metropolis Algorithm for a number of codes and found that the Algorithm performed very well in comparison to previously known experimental results.

  • Search Graph Formulation and Hasting's Generalization of Metropolis Algorithm For Solving SVP
    2013
    Co-Authors: K. B. Ajitha Shenoy, Somenath Biswas, Piyush P. Kurur
    Abstract:

    Shortest Lattice Vector Problem (SVP) has numer- ous applications spanning from robotics to computational num- ber theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the prob- lem that runs in polynomial time. What one normally uses is the LLL Algorithm which, although a polynomial time Algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Hasting's generalization of the Metropolis Algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We also proved that our search space graphs for SVP has mag- nification greater than half. We have implemented the Metropo- lis Algorithm and Hasting's generalization of the Metropolis al- gorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL Algorithm.

  • Metropolis Algorithm for solving shortest lattice vector problem svp
    International Conference Hybrid Intelligent Systems, 2011
    Co-Authors: Shenoy K B Ajitha, Somenath Biswas, Piyush P. Kurur
    Abstract:

    In this paper we study the suitability of the Metropolis Algorithm and its generalization for solving the shortest lattice vector problem (SVP). SVP has numerous applications spanning from robotics to computational number theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the problem that runs in polynomial time. What one normally uses is the LLL Algorithm which, although a polynomial time Algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Metropolis Algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We can use this search space formulation for some other classes of evolutionary Algorithms, e.g., for genetic and go-with-the-winner Algorithms. We have implemented the Metropolis Algorithm and Hasting's generalization of Metropolis Algorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL Algorithm.

  • HIS - Metropolis Algorithm for solving shortest lattice vector problem (SVP)
    2011 11th International Conference on Hybrid Intelligent Systems (HIS), 2011
    Co-Authors: Shenoy K B Ajitha, Somenath Biswas, Piyush P. Kurur
    Abstract:

    In this paper we study the suitability of the Metropolis Algorithm and its generalization for solving the shortest lattice vector problem (SVP). SVP has numerous applications spanning from robotics to computational number theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the problem that runs in polynomial time. What one normally uses is the LLL Algorithm which, although a polynomial time Algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Metropolis Algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We can use this search space formulation for some other classes of evolutionary Algorithms, e.g., for genetic and go-with-the-winner Algorithms. We have implemented the Metropolis Algorithm and Hasting's generalization of Metropolis Algorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL Algorithm.

Xiaofan Zeng - One of the best experts on this subject based on the ideXlab platform.

  • uncertainty assessment and optimization of hydrological model with the shuffled complex evolution Metropolis Algorithm an application to artificial neural network rainfall runoff model
    Stochastic Environmental Research and Risk Assessment, 2013
    Co-Authors: Jun Guo, Jianzhong Zhou, Lixiang Song, Qiang Zou, Xiaofan Zeng
    Abstract:

    Assessment of parameter and predictive uncertainty of hydrologic models is an essential part in the field of hydrology. However, during the past decades, research related to hydrologic model uncertainty is mostly done with conceptual models. As is accepted that uncertainty in model predictions arises from measurement errors associated with the system input and output, from model structural errors and from problems with parameter estimation. Unfortunately, non-conceptual models, such as black-box models, also suffer from these problems. In this paper, we take the artificial neural network (ANN) rainfall-runoff model as an example, and the Shuffled Complex Evolution Metropolis Algorithm (SCEM-UA) is employed to analysis the parameter and predictive uncertainty of this model. Furthermore, based on the results of uncertainty assessment, we finally arrive at a simpler incomplete-connection artificial neural network (ICANN) model as well as with better performance compared to original ANN rainfall-runoff model. These results not only indicate that SCEM-UA can be a useful tool for uncertainty analysis of ANN model, but also prove that uncertainty does exist in ANN rainfall-runoff model. Additionally, in some way, it presents that the ICANN model is with smaller uncertainty than the original ANN model.