Search

Binary matrix factorization is an essential tool for identifying discrete patterns in binary data. In this paper, we consider the rank-k binary matrix factorization problem (k-BMF) under Boolean arithmetic: we are given an n × m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n × k and k × m, respectively, which minimize the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and two exponential size integer programs (IPs) for k-BMF and show that the compact IP has a weak linear programming (LP) relaxation, whereas the exponential size IPs have a stronger equivalent LP relaxation. We introduce a new objective function, which differs from the traditional squared Frobenius objective in attributing a weight to zero entries of the input matrix that is proportional to the number of times the zero is erroneously covered in a rank-k factorization. For one of the exponential size Ips, we describe a computational approach based on column generation. Experimental results on synthetic and real-world data sets suggest that our integer programming approach is competitive against available methods for k-BMF and provides accurate low-error factorizations. Funding: O. Günlük was partially supported by the Office of Naval Research [Grant N00014-21-1-2575]. R. Á. Kovács was supported by a doctoral scholarship from The Alan Turing Institute under the EPSRC [Grant EP/N510129/1] and the Office for National Statistics. R. A. Hauser was supported by The Alan Turing Institute under the EPSRC [Grant EP/N510129/1]. [ABSTRACT FROM AUTHOR]

Aims Right ventricular free wall (RVFWLS) and four-chamber longitudinal strain (RV4CLS) are associated with adverse events in various patient populations including patients with heart failure (HF). We sought to investigate the prognostic value of RVFWLS and RV4CLS for the development of incident HF in participants from the general population. Methods and results Participants from the 5th Copenhagen City Heart Study (2011–2015) without known chronic ischaemic heart disease or HF at baseline were included. RVFWLS and RV4CLS were obtained using two-dimensional speckle-tracking echocardiography from the right ventricular (RV)-focused apical four-chamber view. The primary endpoint was incident HF. Among 2740 participants (mean age 54 ± 17 years, 42% male), 43 (1.6%) developed HF during a median follow-up of 5.5 years (IQR 4.5–6.3). Both RVFWLS and RV4CLS were associated with an increased risk of incident HF during follow-up independent of age, sex, hypertension, diabetes, body mass index and tricuspid annular plane systolic excursion (TAPSE), (HR 1.06, 95%CI 1.00–1.11, P = 0.034, per 1% absolute decrease and HR 1.14, 95%CI 1.05–1.23, P = 0.001, per 1% absolute decrease, respectively). Left ventricular ejection fraction (LVEF) modified the association between RV4CLS and incident HF (P for interaction = 0.016) such that RV4CLS was only of prognostic importance among those with LVEF < 55% (HR 1.21, 95%CI 1.11–1.33, P < 0.001 vs. HR 0.94, 95%CI 0.80–1.10, P = 0.43 in patients with LVEF ≥ 55%). Conclusion In participants from the general population, both RVFWLS and RV4CLS were associated with a greater risk of incident HF independent of important baseline characteristics and TAPSE, and LVEF modified the relationship between RV4CLS and incident HF. [ABSTRACT FROM AUTHOR]

Aim: To promote the implementation of right ventricular (RV) longitudinal strain in clinical practice, we sought to propose normal values for RV free wall (RVFWLS) and four-chamber longitudinal strain (RV4CLS) and investigate the association with clinical and echocardiographic parameters in participants from the general population. Methods and Results: Participants from the 5th Copenhagen City Heart Study (2011–2015)—a prospective cohort study—with available RV longitudinal strain measurements were included. RVFWLS and RV4CLS were assessed using two-dimensional speckle-tracking echocardiography. In total, 2951 participants were included. Amongst 1297 participants without cardiovascular disease or risk factors (median age 44, 63% female), mean values of RVFWLS and RV4CLS were − 26.7% ± 5.2 (95% prediction interval (PI) − 36.9, − 16.5) and − 21.7% ± 3.4 (95%PI − 28.4, − 15.0), respectively. Women had significantly higher absolute values of RVFWLS and RV4CLS than men (mean − 27.5 ± 5.5 vs. − 25.4 ± 4.5, p < 0.001 and − 22.3 ± 3.5 vs. − 20.6 ± 3.0, p < 0.001, respectively). Absolute values of RVFWLS but not RV4CLS decreased significantly with increasing age in unadjusted linear regression. Tricuspid annular plane systolic excursion, RV s' and left ventricular global longitudinal strain were the most influential parameters associated with both RVFWLS and RV4CLS in multiple linear regression. Participants with cardiovascular disease (n = 1531) had a higher proportion of abnormal values of RVFWLS and RV4CLS compared to the healthy population (8% vs. 4%, p < 0.001 and 8% vs. 3%, p < 0.001, respectively). Conclusion: This study proposed normal age- and sex-based values of RVFWLS and RV4CLS in a healthy population sample and showed significant sex differences in both measurements across ages. [ABSTRACT FROM AUTHOR]

Quasi-Newton methods employ an update rule that gradually improves the Hessian approximation using the already available gradient evaluations. We propose higher-order secant updates which generalize this idea to higher-order derivatives, approximating, for example, third derivatives (which are tensors) from given Hessian evaluations. Our generalization is based on the observation that quasi-Newton updates are least-change updates satisfying the secant equation, with different methods using different norms to measure the size of the change. We present a full characterization for least-change updates in weighted Frobenius norms (satisfying an analogue of the secant equation) for derivatives of arbitrary order. Moreover, we establish convergence of the approximations to the true derivative under standard assumptions and explore the quality of the generated approximations in numerical experiments. [ABSTRACT FROM AUTHOR]

Network constraints play a key role in the price finding mechanism for European Power Markets, but historical data is very sparse and usually insufficient for many quantitative applications. We reconstruct the constraints data, known as the Power Transmission Distribution Factors (PTDFs) and Remaining Available Margins (RAMs), by first recovering the underlying time dependent signals known as the Generation Shift Keys (GSKs) and Phase Angles (PAs), and the electricity grid characteristics, via a mathematical optimisation problem. This is solved by exploiting marginal convexity in certain subspaces via alternating minimisation. The GSKs and PAs are then mapped to the PTDFs and RAMs, using the grid structure. Our reconstruction achieves in-sample relative errors of 22.3% and 15.9% for the PTDFs and RAMs respectively, while the out-of-sample ones are 25.4% and 18.1% respectively. We further show that our model outperforms the naive approach, and that the reconstructed GSKs and PAs recover specific structure. [ABSTRACT FROM AUTHOR]

Background Left atrial (LA) strain parameters have been demonstrated to be valuable predictors of atrial fibrillation (AF) in several patient cohorts. The purpose of this study was to investigate whether LA strain, assessed by two-dimensional speckle-tracking echocardiography, can be used to predict the development of AF in the general population. Methods and results This prospective longitudinal study included 4466 participants from the fifth Copenhagen City Heart Study. All participants underwent a health examination, including echocardiographic measurements of LA strain. Participants with prevalent AF at baseline were excluded. The primary endpoint was incident AF. During a median follow-up period of 5.3 years, 154 (4.3%) participants developed AF. In univariable analysis, peak atrial longitudinal strain (PALS), peak atrial contraction strain (PACS), and LA strain during the conduit phase were significantly associated with the development of AF. PALS [hazard ratio (HR) 1.05, 95% confidence interval (CI) (1.03–1.07), P  < 0.001, per 1% decrease] and PACS (HR 1.08, 95% CI (1.05–1.12), P  < 0.001, per 1% decrease] remained independent predictors of AF in multivariable analysis. In addition, PALS and PACS remained significantly associated with AF development even in participants with normal-sized atria and normal left ventricular (LV) systolic function. Conclusion In the general population, PALS and PACS independently predict incident AF. These findings remained consistent even in participants with normal-sized LA and normal LV systolic function. [ABSTRACT FROM AUTHOR]

Aims  Left atrial (LA) function assessed by two-dimensional speckle-tracking echocardiography has shown increasing clinical and prognostic significance. We sought to establish age- and sex-based normative values of LA strain in the general population and to assess the prognostic yield of lower limits of normality of LA strain in relation to future atrial fibrillation (AF). Methods and results  We determined normative values of peak atrial longitudinal strain (PALS), peak atrial contraction strain (PACS), and LA strain during the conduit phase (LACS) in 1641 healthy participants included in the fifth Copenhagen City Heart Study. In a secondary analysis, a validation cohort of 2016 participants, regardless of health status, were included to assess the prognostic value of the established reference values. In the healthy cohort, median age was 46 years (interquartile range 32–57), 62% were female. Median PALS, PACS, and LACS and corresponding limits of normality in the healthy participants were 39.4% (23.0–67.6%), 15.5% (6.4–28.0%), and 23.7% (8.8–44.8%), respectively. There was a tendency of lower values of PALS and LACS in males and older participants, while PACS tended to increase with advancing age. The established lower limits of normality showed high specificity (range 93–94%) regarding future AF, implying a low risk of developing AF in participants with LA strain above the lower limits of normality in their respective sex and age group. Conclusion  We report normal values for LA strain stratified by sex and age. The lower limits of normality showed high specificity regarding future AF. [ABSTRACT FROM AUTHOR]

Aims: The present study had two aims: (i) compare echocardiographic parameters in COVID‐19 patients with matched controls and (2) assess the prognostic value of measures of left (LV) and right ventricular (RV) function in relation to COVID‐19 related death. Methods and results: In this prospective multicentre cohort study, 214 consecutive hospitalized COVID‐19 patients underwent an echocardiographic examination (by pre‐determined research protocol). All participants were successfully matched 1:1 with controls from the general population on age, sex, and hypertension. Mean age of the study sample was 69 years, and 55% were male participants. LV and RV systolic function was significantly reduced in COVID‐19 cases as assessed by global longitudinal strain (GLS) (16.4% ± 4.3 vs. 18.5% ± 3.0, P < 0.001), tricuspid annular plane systolic excursion (TAPSE) (2.0 ± 0.4 vs. 2.6 ± 0.5, P < 0.001), and RV strain (19.8 ± 5.9 vs. 24.2 ± 6.5, P = 0.004). All parameters remained significantly reduced after adjusting for important cardiac risk factors. During follow‐up (median: 40 days), 25 COVID‐19 cases died. In multivariable Cox regression reduced TAPSE [hazard ratio (HR) = 1.18, 95% confidence interval (CI) [1.07–1.31], P = 0.002, per 1 mm decrease], RV strain (HR = 1.64, 95%CI[1.02;2.66], P = 0.043, per 1% decrease) and GLS (HR = 1.20, 95%CI[1.07–1.35], P = 0.002, per 1% decrease) were significantly associated with COVID‐19‐related death. TAPSE and GLS remained significantly associated with the outcome after restricting the analysis to patients without prevalent heart disease. Conclusions: RV and LV function are significantly impaired in hospitalized COVID‐19 patients compared with matched controls. Furthermore, reduced TAPSE and GLS are independently associated with COVID‐19‐related death. [ABSTRACT FROM AUTHOR]

This paper introduces Memory-limited Online Subspace Estimation Scheme (MOSES) for both estimating the principal components of streaming data and reducing its dimension. More specifically, in various applications such as sensor networks, the data vectors are presented sequentially to a user who has limited storage and processing time available. Applied to such problems, MOSES can provide a running estimate of leading principal components of the data that has arrived so far and also reduce its dimension. MOSES generalises the popular incremental Singular Vale Decomposition (iSVD) to handle thin blocks of data, rather than just vectors. This minor generalisation in part allows us to complement MOSES with a comprehensive statistical analysis, thus providing the first theoretically-sound variant of iSVD, which has been lacking despite the empirical success of this method. This generalisation also enables us to concretely interpret MOSES as an approximate solver for the underlying non-convex optimisation program. We find that MOSES consistently surpasses the state of the art in our numerical experiments with both synthetic and real-world datasets, while being computationally inexpensive. [ABSTRACT FROM AUTHOR]

Principal component analysis (PCA) is an important pattern recognition and dimensionality reduction tool in many applications. Principal components are computed as eigenvectors of a maximum likelihood covariance |$\widehat{\varSigma }$| that approximates a population covariance |$\varSigma$|⁠ , and these eigenvectors are often used to extract structural information about the variables (or attributes) of the studied population. Since PCA is based on the eigendecomposition of the proxy covariance |$\widehat{\varSigma }$| rather than the ground-truth |$\varSigma$|⁠ , it is important to understand the approximation error in each individual eigenvector as a function of the number of available samples. The combination of recent results of Koltchinskii & Lounici (2017, Bernoulli , 23 , 110–133) and Yu et al. (2015, Biometrika , 102 , 315–323) yields such bounds. In the present paper we sharpen these bounds and show that eigenvectors can often be reconstructed to a required accuracy from a sample of strictly smaller size order. [ABSTRACT FROM AUTHOR]

Principal component analysis (PCA) finds the best linear representation of data and is an indispensable tool in many learning and inference tasks. Classically, principal components of a dataset are interpreted as the directions that preserve most of its “energy,” an interpretation that is theoretically underpinned by the celebrated Eckart–Young–Mirsky theorem. This paper introduces many other ways of performing PCA, with various geometric interpretations, and proves that the corresponding family of nonconvex programs has no spurious local optima, while possessing only strict saddle points. These programs therefore loosely behave like convex problems and can be efficiently solved to global optimality, for example, with certain variants of the stochastic gradient descent. Beyond providing new geometric interpretations and enhancing our theoretical understanding of PCA, our findings might pave the way for entirely new approaches to structured dimensionality reduction, such as sparse PCA and nonnegative matrix factorization. More specifically, we study an unconstrained formulation of PCA using determinant optimization that might provide an elegant alternative to the deflating scheme commonly used in sparse PCA. [ABSTRACT FROM AUTHOR]

We extend Relative Robust Portfolio Optimization models to allow portfolios to optimize their performance when considered relative to a set of benchmarks. We do this in a minimum volatility setting, where we model regret directly as the maximum difference between our volatility and that of a given benchmark. Portfolio managers are also given the option of computing regret as a proportion of the benchmark’s performance, which is more in line with market practice than other approaches suggested in the literature. Furthermore, we propose using regret as an extra constraint rather than as a brand new objective function, so practitioners can maintain their current framework. We also look into how such a triple optimization problem can be solved or at least approximated for a general class of objective functions and uncertainty and benchmark sets. Finally, we illustrate the benefits of this approach by examining its performance against other common methods in the literature in several equity markets. [ABSTRACT FROM AUTHOR]

Considering two optimally aligned random sequences, we investigate the effect on the alignment score caused by changing a random letter in one of the two sequences. Using this idea in conjunction with large deviations theory, we show that in alignments with a low proportion of gaps the optimal alignment is locally unique in most places with high probability. This has implications in the design of recently pioneered alignment methods that use the local uniqueness as a homology indicator. [ABSTRACT FROM AUTHOR]

We consider the conic feasibility problem associated with the linear homogeneous system Ax≤0, x≠0. The complexity of iterative algorithms for solving this problem depends on a condition number C( A). When studying the typical behavior of algorithms under stochastic input, one is therefore naturally led to investigate the fatness of the tails of the distribution of C( A). Introducing the very general class of uniformly absolutely continuous probability models for the random matrix A, we show that the distribution tails of C( A) decrease at algebraic rates, both for the Goffin–Cheung–Cucker number C G and the Renegar number C R. The exponent that drives the decay arises naturally in the theory of uniform absolute continuity, which we also develop in this paper. In the case of C G, we also discuss lower bounds on the tail probabilities and show that there exist absolutely continuous input models for which the tail decay is subalgebraic. [ABSTRACT FROM AUTHOR]

Considering iterative sequences that arise when approximate solutions xk to a numerical problem are updated by xk+1 = xk +v(xk), where v is a differentiable vector field, we derive necessary and sufficient conditions for such discrete processes to converge to a stationary point of v at different Q-rates in terms of a similar notion of fast convergence for the corresponding continuous processes. [ABSTRACT FROM AUTHOR]

Consider the random variable Ln defined as the length of a longest common subsequence of two random strings of length n and whose random characters are independent and identically distributed over a finite alphabet. Chvátal and Sankoff showed that the limit γ = limn→∞ E[Ln]/n is well defined. The exact value of this constant is not known, but various methods for the computation of upper and lower bounds have been discussed in the literature. Even so, high-precision bounds are hard to come by. In this paper we discuss how large deviation theory can be used to derive a consistent sequence of upper bounds, (qm)mϵN, on γ, and how Monte Carlo simulation can be used in theory to compute estimates, qˆm, of the qm, such that, for given Ξ > 0 and Λ ϵ (0, 1), we have P[γ < qˆ < γ + Ξ] ≥ Λ. In other words, with high probability the result is an upper bound that approximates y to high precision. We establish O ((1 - Λ)-1 Ξ -(4+ε)) as a theoretical upper bound on the complexity of computing qˆm to the given level of accuracy and confidence. Finally, we discuss a practical heuristic based on our theoretical approach and discuss its empirical behavior. [ABSTRACT FROM AUTHOR]

A classical theorem by Block and Levin (Block, H. D., S. A. Levin. 1970. On the boundedness of an iterative procedure for solving a system of linear inequalities. Proc. Amer. Math. Soc. 26 229-235) states that certain variants of the relaxation method for solving systems of linear inequalities generate bounded sequences of intermediate solutions, even when applied to infeasible systems. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying the bound as a function of the input data. [ABSTRACT FROM AUTHOR]

In this paper we study the distribution of $\mathscr C(A)$ and $\log\mathscr C(A)$, where $\mathscr C(A)$ is a condition number for the linear conic system $Ax\leq 0$, $x\neq 0$, with $A\in\Bbb R^{n\times m}$. For Gaussian matrices $A$ we develop both upper and lower bounds on the decay rates of the distribution tails of $\mathscr C(A)$, showing that ${\bf P}\left[\mathscr C(A)\geq t\right]\sim c/t$ for large $t$, where $c$ is a factor that depends only on the problem dimensions $(m,n)$. Using these bounds, we derive moment estimates for $\mathscr C(A)$ and $\log\mathscr C(A)$ and prove various limit theorems for the cases where $m$ and/or $n$ are large. Combined with condition number based complexity analyses, our results yield tail information on the distribution of running times for interior-point or relaxation methods designed to solve the feasibility problem $Ax\leq 0$, $x\neq 0$. [ABSTRACT FROM AUTHOR]

Abstract. This paper is about an intriguing property of the continuous Newton-Raphson method for the minimisation of a continuous objective function f: if x is a point in the domain of attraction of a strict local minimiser z*, then the flux line of the Newton-Raphson flow that starts in x approaches z* from a direction that depends only on the behavior of / in arbitrarily small neighborhoods around x and z*. In fact, if f is a sufficiently benign perturbation of f on an open region D not containing z, then the two flux lines through z defined by the Newton-Raphson vector fields that correspond to fand f differ from one another only within D. [ABSTRACT FROM AUTHOR]

The subject of this paper concerns differential-geometric properties of the Nesterov–Todd search direction for linear optimization over symmetric cones. In particular, we investigate the rescaled asymptotics of the associated flow near the central path. Our results imply that the Nesterov–Todd direction arises as the solution of a Newton system defined in terms of a certain transformation of the primal-dual feasible domain. This transformation has especially appealing properties which generalize the notion of weighted analytic centers for linear programming. [ABSTRACT FROM AUTHOR]

Self-scaled barrier functions on self-scaled cones were axiomatically introduced by Nesterov and Todd in 1994 as a tool for the construction of primal—dual long-step interior point algorithms. This paper provides firm foundations for these objects by exhibiting their symmetry properties, their close ties with the symmetry groups of their domains of definition, and subsequently their decomposition into irreducible parts and their algebraic classification theory. In the first part we recall the characterization of the family of self-scaled cones as the set of symmetric cones and develop a primal—dual symmetric viewpoint on self-scaled barriers, results that were first discovered by the second author. We then show in a short, simple proof that any pointed, convex cone decomposes into a direct sum of irreducible components in a unique way, a result which can also be of independent interest. We then proceed to showing that any self-scaled barrier function decomposes, in an essentially unique way, into a direct sum of self-scaled barriers defined on the irreducible components of the underlying symmetric cone. Finally, we present a complete algebraic classification of self-scaled barrier functions using the correspondence between symmetric cones and Euclidean—Jordan algebras. [ABSTRACT FROM AUTHOR]

Examines the special class of self-scaled barriers which are defined on irreducible symmetric cones. Domain of definition of a self-scaled barrier; Preliminary notions; Information on the self-scaled barriers for irreducible symmetric cones.