More Like this

1. The Global Optimization Geometry of Low-Rank Matrix Optimization

   https://doi.org/10.1109/TIT.2021.3049171  

   Zhu, Zhihui; Li, Qiuwei; Tang, Gongguo; Wakin, Michael B. (February 2021, IEEE Transactions on Information Theory)

   null (Ed.)
2. OPTIMIZATION OF THE HIGUCHI METHOD

   https://doi.org/10.29121/granthaalayah.v9.i11.2021.4393  

   Wanliss, J.; Arriaza, R. Hernandez; Wanliss, G.; Gordon, S. (November 2021, International Journal of Research -GRANTHAALAYAH)

   Background and Objective: Higuchi’s method of determining fractal dimension (HFD) occupies a valuable place in the study of a wide variety of physical signals. In comparison to other methods, it provides more rapid, accurate estimations for the entire range of possible fractal dimensions. However, a major difficulty in using the method is the correct choice of tuning parameter (kmax) to compute the most accurate results. In the past researchers have used various ad hoc methods to determine the appropriate kmax choice for their particular data. We provide a more objective method of determining, a priori, the best value for the tuning parameter, given a particular length data set. Methods: We create numerous simulations of fractional Brownian motion to perform Monte Carlo simulations of the distribution of the calculated HFD. Results: Experimental results show that HFD depends not only on kmax but also on the length of the time series, which enable derivation of an expression to find the appropriate kmax for an input time series of unknown fractal dimension. Conclusion: The Higuchi method should not be used indiscriminately without reference to the type of data whose fractal dimension is examined. Monte Carlo simulations with different fractional Brownian motions increases the confidence of evaluation results. 

   more » « less
3. The Communication Complexity of Optimization

   https://doi.org/10.1137/1.9781611975994.106  

   Vempala, Santosh S.; Wang, Ruosong; Woodruff, David P. (January 2020, ACM-SIAM Symposium on Discrete Algorithms)

   null (Ed.)

   We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator together with s servers P1, …, Ps, the i-th of which holds a subset A(i) x = b(i) of ni constraints of a linear system in d variables, and the coordinator would like to output an x ϵ ℝd for which A(i) x = b(i) for i = 1, …, s. We assume each coefficient of each constraint is specified using L bits. We first resolve the randomized and deterministic communication complexity in the point-to-point model of communication, showing it is (d2 L + sd) and (sd2L), respectively. We obtain similar results for the blackboard communication model. As a result of independent interest, we show the probability a random matrix with integer entries in {–2L, …, 2L} is invertible is 1–2−Θ(dL), whereas previously only 1 – 2−Θ(d) was known. When there is no solution to the linear system, a natural alternative is to find the solution minimizing the ℓp loss, which is the ℓp regression problem. While this problem has been studied, we give improved upper or lower bounds for every value of p ≥ 1. One takeaway message is that sampling and sketching techniques, which are commonly used in earlier work on distributed optimization, are neither optimal in the dependence on d nor on the dependence on the approximation ε, thus motivating new techniques from optimization to solve these problems. Towards this end, we consider the communication complexity of optimization tasks which generalize linear systems, such as linear, semi-definite, and convex programming. For linear programming, we first resolve the communication complexity when d is constant, showing it is (sL) in the point-to-point model. For general d and in the point-to-point model, we show an Õ(sd3L) upper bound and an (d2 L + sd) lower bound. In fact, we show if one perturbs the coefficients randomly by numbers as small as 2−Θ(L), then the upper bound is Õ(sd2L) + poly(dL), and so this bound holds for almost all linear programs. Our study motivates understanding the bit complexity of linear programming, which is related to the running time in the unit cost RAM model with words of O(log(nd)) bits, and we give the fastest known algorithms for linear programming in this model. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975994.106 

   more » « less
4. Optimization of the Sherrington--Kirkpatrick Hamiltonian

   https://doi.org/10.1137/20M132016X  

   Montanari, Andrea (January 2021, SIAM Journal on Computing)

   null (Ed.)
5. Optimization of the Sherrington-Kirkpatrick Hamiltonian

   https://doi.org/10.1109/FOCS.2019.00087  

   Montanari, Andrea (November 2019, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS))