A note on “Reducing the number of binary variables in cutting stock problems”

This study proposes a deterministic model to solve the two-dimensional cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with $m$ stocks and $n$ cutting rectangles requires $2n^{2}+n(m+1)$ binary variables in the traditional model. In contrast, the proposed model uses $n^{2}+n\lceil {\log _2 m}\rceil $ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.     

On Compact Wavelet Matrices of Rank m and of Order and Degree N

A new parametrization (one-to-one onto map) of compact wavelet matrices of rank $m$ and of order and degree $N$ is proposed in terms of coordinates in the Euclidian space $\mathbb {C}^{(m-1)N}$ . The developed method depends on Wiener–Hopf factorization of corresponding unitary matrix functions and allows to construct compact wavelet matrices efficiently. Some applications of the proposed method are discussed.     

On the computation of all eigenvalues for the eigenvalue complementarity problem

In this paper, a parametric algorithm is introduced for computing all eigenvalues for two Eigenvalue Complementarity Problems discussed in the literature. The algorithm searches a finite number of nested intervals \([\bar{l}, \bar{u}]\) in such a way that, in each iteration, either an eigenvalue is computed in \([\bar{l}, \bar{u}]\) or a certificate of nonexistence of an eigenvalue in \([\bar{l}, \bar{u}]\) is provided. A hybrid method that combines an enumerative method [1] and a semi-smooth algorithm [2] is discussed for dealing with the Eigenvalue Complementarity Problem over an interval \([\bar{l}, \bar{u}]\) . Computational experience is presented to illustrate the efficacy and efficiency of the proposed techniques.     

Reorthogonalization for the Golub–Kahan–Lanczos bidiagonal reduction

The Golub–Kahan–Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of $X \in \mathbb{R }^{m \times n}, m \ge n$ , given by $$\begin{aligned} X = UBV^T \end{aligned}$$ where $U \in \mathbb{R }^{m \times n}$ is left orthogonal, $V \in \mathbb{R }^{n \times n}$ is orthogonal, and $B \in \mathbb{R }^{n \times n}$ is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of $U$ and $V$ tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257–2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices $U$ and $V$ is shown to be very effective by the results presented here. Supposing that $V$ is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q–R factorization of $\left( \begin{array}{c} 0_{n \times k} \\ X V_k \end{array}\right) $ where $V_k = V(:,1:k)$ . That model is used to show that if $\varepsilon _M $ is the machine unit and $$\begin{aligned} \bar{\eta }= \Vert \mathbf{tril }(I-V^T\!~V)\Vert _F, \end{aligned}$$ where $\mathbf{tril }(\cdot )$ is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix $X + \delta X$ , $\Vert \delta X\Vert _F = \mathcal O (\varepsilon _M + \bar{\eta }) \Vert X\Vert _F$ ; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.     

Adelic Multiresolution Analysis, Construction of Wavelet Bases and Pseudo-Differential Operators

In our previous paper, the Haar multiresolution analysis (MRA) $\{V_{j}\}_{j\in \mathbb {Z}}$ in $L^{2}(\mathbb {A})$ was constructed, where $\mathbb {A}$ is the adele ring. Since $L^{2}(\mathbb {A})$ is the infinite tensor product of the spaces $L^{2}({\mathbb {Q}}_{p})$ , p=∞,2,3,…, the adelic MRA has some specific properties different from the corresponding finite-dimensional ones. Nevertheless, this infinite-dimensional MRA inherits almost all basic properties of the finite-dimensional case. In this paper we derive explicit formulas for bases in V _j , $j\in \mathbb {Z}$ , and for the wavelet bases generated by the above-mentioned adelic MRA. In view of the specific properties of the adelic MRA, there arise some technical problems in the construction of wavelet bases. These problems were solved with the aid of the operator formalization of the process of generation of wavelet bases. We study the spectral properties of the fractional operator introduced by S. Torba and W.A. Zúñiga-Galindo. We prove that the constructed wavelet functions are eigenfunctions of this fractional operator. This paper, as well as our previous paper, introduces new ideas to construct different infinite-dimensional MRAs. Our results can be used in the theory of adelic pseudo-differential operators and equations over the ring of adeles and in adelic models in physics.     

A unified approach for minimizing composite norms

We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem $$\begin{aligned} \begin{array}{ll} \min \limits _{X\in \mathbb{R }^{m\times n}}&\mu _1\Vert \sigma (\mathcal{F }(X)-G)\Vert _\alpha +\mu _2\Vert \mathcal{C }(X)-d\Vert _\beta ,\\ \text{ subject} \text{ to}&\mathcal{A }(X)-b\in \mathcal{Q }, \end{array} \end{aligned}$$ where $\sigma (X)$ denotes the vector of singular values of $X \in \mathbb{R }^{m\times n}$ , the matrix norm $\Vert \sigma (X)\Vert _{\alpha }$ denotes either the Frobenius, the nuclear, or the $\ell _2$ -operator norm of $X$ , the vector norm $\Vert .\Vert _{\beta }$ denotes either the $\ell _1$ -norm, $\ell _2$ -norm or the $\ell _{\infty }$ -norm; $\mathcal{Q }$ is a closed convex set and $\mathcal{A }(.)$ , $\mathcal{C }(.)$ , $\mathcal{F }(.)$ are linear operators from $\mathbb{R }^{m\times n}$ to vector spaces of appropriate dimensions. Basis pursuit, matrix completion, robust principal component pursuit (PCP), and stable PCP problems are all special cases of the composite norm minimization problem. Thus, FALC is able to solve all these problems in a unified manner. We show that any limit point of FALC iterate sequence is an optimal solution of the composite norm minimization problem. We also show that for all $\epsilon >0$ , the FALC iterates are $\epsilon $ -feasible and $\epsilon $ -optimal after $\mathcal{O }(\log (\epsilon ^{-1}))$ iterations, which require $\mathcal{O }(\epsilon ^{-1})$ constrained shrinkage operations and Euclidean projection onto the set $\mathcal{Q }$ . Surprisingly, on the problem sets we tested, FALC required only $\mathcal{O }(\log (\epsilon ^{-1}))$ constrained shrinkage, instead of the $\mathcal{O }(\epsilon ^{-1})$ worst case bound, to compute an $\epsilon $ -feasible and $\epsilon $ -optimal solution. To best of our knowledge, FALC is the first algorithm with a known complexity bound that solves the stable PCP problem.     

A unified algorithm for mixed l_{2,p}-minimizations and its application in feature selection

Recently, matrix norm $l_{2,1}$ has been widely applied to feature selection in many areas such as computer vision, pattern recognition, biological study and etc. As an extension of $l_1$ norm, $l_{2,1}$ matrix norm is often used to find jointly sparse solution. Actually, computational studies have showed that the solution of $l_p$ -minimization ( $0<p<1$ ) is sparser than that of $l_1$ -minimization. The generalized $l_{2,p}$ -minimization ( $p\in (0,1]$ ) is naturally expected to have better sparsity than $l_{2,1}$ -minimization. This paper presents a type of models based on $l_{2,p}\ (p\in (0, 1])$ matrix norm which is non-convex and non-Lipschitz continuous optimization problem when $p$ is fractional ( $0<p<1$ ). For all $p$ in $(0, 1]$ , a unified algorithm is proposed to solve the $l_{2,p}$ -minimization and the convergence is also uniformly demonstrated. In the practical implementation of algorithm, a gradient projection technique is utilized to reduce the computational cost. Typically different $l_{2,p}\ (p\in (0,1])$ are applied to select features in computational biology.     

Units of compatible nearrings

We study singly-generated wavelet systems on ${\mathbb {R}^2}$ that are naturally associated with rank-one wavelet systems on the Heisenberg group N. We prove a necessary condition on the generator in order that any such system be a Parseval frame. Given a suitable subset I of the dual of N, we give an explicit construction for Parseval frame wavelets that are associated with I. We say that ${g\in L^2(I\times \mathbb {R})}$ is Gabor field over I if, for a.e. ${\lambda \in I}$ , |??|^1/2 g(??, ·) is the Gabor generator of a Parseval frame for ${L^2(\mathbb {R})}$ , and that I is a Heisenberg wavelet set if every Gabor field over I is a Parseval frame (mother-)wavelet for ${L^2(\mathbb {R}^2)}$ . We then show that I is a Heisenberg wavelet set if and only if I is both translation congruent with a subset of the unit interval and dilation congruent with the Shannon set.