A New Algorithm for a Field Splitting Problem in Intensity-Modulated Radiation Therapy

Intensity-modulated radiation therapy (IMRT) is a modern cancer treatment technique with which optimized radiation fluence distributions, called intensity maps (IMs), are delivered to the target tumors via the help of a device called multileaf collimator (MLC), in order to produce homogeneous dose distributions of a prescribed amount at the target while sparing the surrounding organs and tissue. Due to the maximum leaf spread constraint of the MLCs, IMs whose widths exceed a given threshold cannot be delivered as a whole, and thus must be split into multiple subfields. The field splitting problems in IMRT normally aim to minimize the total beam-on time (i.e. the total time when a patient is exposed to actual irradiation during the delivery) of the resulting subfields. In this paper, we present a new efficient polynomial time algorithm for a general field splitting problem with guaranteed output optimality.     

Efficient intensity map splitting algorithms for intensity-modulated radiation therapy

In this paper, we study several interesting intensity map splitting (IMSp) problems that arise in Intensity-Modulated Radiation Therapy (IMRT), a state-of-the-art radiation therapy technique for cancer treatments. In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of an MLC may require that a large intensity map be split into several abutting sub-IMs each being delivered separately, which results in prolonged treatment time. Few IM splitting techniques reported in the literature have addressed the issue of treatment delivery efficiency for large IMs. We develop a unified approach for solving the IMSp problems while minimizing the total beam-on time in various settings. Our basic idea is to formulate the IMSp problem as computing a k-link shortest path in a directed acyclic graph. We carefully characterize the intrinsic structures of the graph, yielding efficient algorithms for the IMSp problems.     

Coupled Path Planning,Region Optimization,and Applications in Intensity-modulated Radiation Therapy

In this paper, we consider an optimization problem in discrete geometry, called coupled path planning (CPP). Given a finite rectangular grid and a non-negative function f defined on the horizontal axis of the grid, we seek two non-crossing monotone paths in the grid, such that the vertical difference between the two paths approximates f in the best possible way. This problem arises in intensity-modulated radiation therapy (IMRT), where f represents an ideal radiation dose distribution and the two coupled paths represent the motion trajectories (or control sequence) of two opposing metal leaves of a delivery device for controlling the area exposed to the radiation source. By finding an optimal control sequence, the CPP problem aims to deliver precisely a prescribed radiation dose, while minimizing the side-effects on the surrounding normal tissue. We present efficient algorithms for different versions of the CPP problems. Our results are based on several new ideas and geometric observations, and substantially improve the solutions based on standard techniques. Implementation results show that our CPP algorithms run fast and produce better quality clinical treatment plans than the previous methods.     

CP and IP approaches to cancer radiotherapy delivery optimization

We consider the problem of decomposing an integer matrix into a positively weighted sum of binary matrices that have the consecutive-ones property. This problem is well-known and of practical relevance. It has an important application in cancer radiation therapy treatment planning: the sequencing of multileaf collimators to deliver a given radiation intensity matrix, representing (a component of) the treatment plan. Two criteria characterise the efficacy of a decomposition: the beam-on time (the length of time the radiation source is switched on during the treatment), and the cardinality (the number of machine set-ups required to deliver the planned treatment). Minimising the former is known to be easy. However finding a decomposition of minimal cardinality is NP-hard. Progress so far has largely been restricted to heuristic algorithms, mostly using linear programming, integer programming and combinatorial enumerative methods as the solving approaches. We present a novel model, with corresponding constraint programming and integer programming formulations. We compare these computationally with previous formulations, and we show that constraint programming performs very well by comparison.     

Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures

We consider the problem of decomposing Intensity Modulated Radiation Therapy (IMRT) fluence maps using rectangular apertures. A fluence map can be represented as an integer matrix, which denotes the intensity profile to be delivered to a patient through a given beam angle. We consider IMRT treatment machinery that can form rectangular apertures using conventional jaws, and hence, do not need sophisticated multi-leaf collimator (MLC) devices. The number of apertures used to deliver the fluence map needs to be minimized in order to treat the patient efficiently. From a mathematical point of view, the problem is equivalent to a minimum cardinality matrix decomposition problem. We propose a combinatorial Benders decomposition approach to solve this problem to optimality. We demonstrate the efficacy of our approach on a set of test instances derived from actual clinical data. We also compare our results with the literature and solutions obtained by solving a mixed-integer programming formulation of the problem.     

Non-negative and sparse spectral clustering

Spectral clustering aims to partition a data set into several groups by using the Laplacian of the graph such that data points in the same group are similar while data points in different groups are dissimilar to each other. Spectral clustering is very simple to implement and has many advantages over the traditional clustering algorithms such as k-means. Non-negative matrix factorization (NMF) factorizes a non-negative data matrix into a product of two non-negative (lower rank) matrices so as to achieve dimension reduction and part-based data representation. In this work, we proved that the spectral clustering under some conditions is equivalent to NMF. Unlike the previous work, we formulate the spectral clustering as a factorization of data matrix (or scaled data matrix) rather than the symmetrical factorization of the symmetrical pairwise similarity matrix as the previous study did. Under the NMF framework, where regularization can be easily incorporated into the spectral clustering, we propose several non-negative and sparse spectral clustering algorithms. Empirical studies on real world data show much better clustering accuracy of the proposed algorithms than some state-of-the-art methods such as ratio cut and normalized cut spectral clustering and non-negative Laplacian embedding.     

A note on improving the performance of approximation algorithms for radiation therapy

The segment minimization problem consists of representing an integer matrix as the sum of the fewest number of integer matrices each of which have the property that the non-zeroes in each row are consecutive. This has direct applications to an effective form of cancer treatment. Using several insights, we extend previous results to obtain constant-factor improvements in the approximation guarantees. We show that these improvements yield better performance by providing an experimental evaluation of all known approximation algorithms using both synthetic and real-world clinical data. Our algorithms are superior for 76% of instances and we argue for their utility alongside the heuristic approaches used in practice.     

A fast beam orientation optimization method that enforces geometric constraints in IMRT for total marrow irradiation

The beam orientation optimization (BOO) problem for intensity‐modulated radiation therapy (IMRT) is the selection of beams for radiation delivery. Conventionally, it is desirable for beams to be spatially separated to ensure a homogeneous dose. However, many BOO approaches yield clustered beams. This issue is especially prevalent for total marrow irradiation (TMI), where the target is very large and spread throughout the patient's body. Based on previous set‐cover formulations of the BOO problem for TMI‐IMRT, we propose an extension that enforces geometric beam constraints by iteratively removing beams violating geometric constraints within the set‐cover framework. After beams are selected, they are used as input to a fluence map optimization solver to obtain optimal fluence maps. Results for a clinical TMI case meet clinical guidelines for target coverage and differentiation of organ and target doses.     

Improving non-negative matrix factorizations through structured initialization

In this paper we explore a recent iterative compression technique called non-negative matrix factorization (NMF). Several special properties are obtained as a result of the constrained optimization problem of NMF. For facial images, the additive nature of NMF results in a basis of features, such as eyes, noses, and lips. We explore various methods for efficiently computing NMF, placing particular emphasis on the initialization of current algorithms. We propose using Spherical K-Means clustering to produce a structured initialization for NMF. We demonstrate some of the properties that result from this initialization and develop an efficient way of choosing the rank of the low-dimensional NMF representation.     

Discover latent discriminant information for dimensionality reduction: Non-negative Sparseness Preserving Embedding

How to define sparse affinity weight matrices is still an open problem in existing manifold learning algorithms. In this paper, we propose a novel unsupervised learning method called Non-negative Sparseness Preserving Embedding (NSPE) for linear dimensionality reduction. Differing from the manifold learning-based subspace learning methods such as Locality Preserving Projections (LPP), Neighbor Preserving Embedding (NPE) and the recently proposed sparse representation based Sparsity Preserving Projections (SPP); NSPE preserves the non-negative sparse reconstruction relationships in low-dimensional subspace. Another novelty of NSPE is the sparseness constraint, which is directly added to control the non-negative sparse representation coefficients. This gives a more ground truth model to imitate the actions of the active neuron cells of V1 of the primate visual cortex on information processing. Although labels are not used in the training steps, the non-negative sparse representation can still discover the latent discriminant information and thus provides better measure coefficients and significant discriminant abilities for feature extraction. Moreover, NSPE is more efficient than the recently proposed sparse representation based SPP algorithm. Comprehensive comparison and extensive experiments show that NSPE has the competitive performance against the unsupervised learning algorithms such as classical PCA and the state-of-the-art techniques: LPP, NPE and SPP.     

Load-balancing spatially located computations using rectangular partitions

Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoffs.     

基于稀疏约束的半监督非负矩阵分解算法

矩阵分解因可以实现大规模数据处理而具有十分广泛的应用。非负矩阵分解(Nonnegative Matrix Factorization,NMF)是一种在约束矩阵元素为非负的条件下进行的分解方法。利用少量已知样本的标注信息和大量未标注样本,并施加稀疏性约束,构造了一种新的算法——基于稀疏约束的半监督非负矩阵分解算法。推导了其有效的更新算法,并证明了该算法的收敛性。在常见的人脸数据库上进行了验证,实验结果表明CNMFS算法相对于NMF和CNMF等算法具有较好的稀疏性和聚类精度。     

基于先验知识的非负矩阵半可解释三因子分解算法

非负矩阵三因子分解是潜在因子模型中的重要组成部分,由于能将原始数据矩阵分解为三个相互约束的潜因子矩阵,被广泛应用于推荐系统、迁移学习等研究领域,但目前还没有非负矩阵三因子分解的可解释性方面的研究工作.鉴于此,将用户评论文本信息当作先验知识,设计了一种基于先验知识的非负矩阵半可解释三因子分解(PE-NMTF)算法.首先利...     

三维非负矩阵因子分解代谢组学数据解析

多维数据解析方法越来越引起人们的重视,非负矩阵因子分解算法已较广泛地用于图像分析。基于PARAFAC模型,将非负矩阵因子分解算法拓展为三维非负矩阵因子分解算法(three dimension non-negative matrix factorization,NMF3)。其原理简明,算法易于执行。与基于向量计算的其他三维化学计量学算法不同,NMF3基于矩阵计算单个元素,所以不必将三维数据平铺处理,就可直接解析,为三维数据解析研究提供了一种全新的思路和方法。应用NMF3解析模拟三维数据和代谢组学数据,结果令人满意。     

Block-Diagonal Approach to Non-Negative Factorization of Sparse Linguistic Matrices and Tensors of Extra-Large Dimension Using the Latent Dirichlet Distribution

This paper describes algorithms for non-negative factorization of sparse matrices and tensors, which is a popular technology in artificial intelligence in general and in computer linguistics in particular. It is proposed to use the latent Dirichlet distribution to reduce matrices and tensors to block-diagonal form for parallelizing computations and accelerating non-negative factorization of linguistic matrices and tensors of extremely large dimension. The proposed model also allows to supplement models with new data without performing non-negative factorization of the entire very large tensor anew from the very beginning.     

赋权图匹配问题的一种新的松弛模型

图匹配是一个NP难(NP-hard)问题. 基于置换矩阵是非负正交矩阵这一经典结论, 提出赋权图匹配(Weighted graph matching, WGM)的双向松弛障碍规划, 理论上证明新模型的解与原模型的解是一致的. 该规划是一个二元连续规划, 它是正交矩阵上的线性优化问题, 同时也是非负矩阵上的凸二次优化问题. 故设计求解新模型的交替迭代算法, 并证明算法的局部收敛性. 数值实验表明, 在匹配精度方面, 新方法强于线性规划方法和特征值分解方法.     

Optimization Algorithms on Subspaces: Revisiting Missing Data Problem in Low-Rank Matrix

Low-rank matrix approximation has applications in many fields, such as 3D reconstruction from an image sequence and 2D filter design. In this paper, one issue with low-rank matrix approximation is re-investigated: the missing data problem. Much effort was devoted to this problem, and the Wiberg algorithm or the damped Newton algorithm were recommended in previous studies. However, the Wiberg or damped Newton algorithms do not suit for large (especially “long”) matrices, because one needs to solve a large linear system in every iteration. In this paper, we revitalize the usage of the Levenberg-Marquardt algorithm for solving the missing data problem, by utilizing the property that low-rank approximation is a minimization problem on subspaces. In two proposed implementations of the Levenberg-Marquardt algorithm, one only needs to solve a much smaller linear system in every iteration, especially for “long” matrices. Simulations and experiments on real data show the superiority of the proposed algorithms. Though the proposed algorithms achieve a high success rate in estimating the optimal solution by random initialization, as illustrated by real examples; it still remains an open issue how to properly do the initialization in a severe situation (that is, a large amount of data is missing and with high-level noise).     

Exploiting inter-operation parallelism for matrix chain multiplication using MapReduce

In this paper, we address the matrix chain multiplication problem, i.e., the multiplication of several matrices. Although several studies have investigated the problem, our approach has some different points. First, we propose MapReduce algorithms that allow us to provide scalable computation for large matrices. Second, we transform the matrix chain multiplication problem from sequential multiplications of two matrices into a single multiplication of several matrices. Since matrix multiplication is associative, this approach helps to improve the performance of the algorithms. To implement the idea, we adopt multi-way join algorithms in MapReduce that have been studied in recent years. In our experiments, we show that the proposed algorithms are fast and scalable, compared to several baseline algorithms.     

基于改进贝叶斯概率模型的推荐算法

针对现有基于矩阵分解的协同过滤推荐系统预测精度与推荐精度较低的问题,提出一种改进的矩阵分解方法与协同过滤推荐系统。首先,将评分矩阵分解为两个非负矩阵,并对评分做归一化处理,使其具有概率语义;然后,采用变分推理法计算贝叶斯概率模型实部后验的分布;最后,搜索相同偏好的用户分组并预测用户的偏好。此外,基于用户向量的稀疏性设计一种低计算复杂度、低存储成本的推荐结果决策算法。基于3组公开数据集的实验结果表明,本算法的预测性能以及推荐系统的效果均优于其他预测算法与推荐算法。     

Bounded matrix factorization for recommender system

Matrix factorization has been widely utilized as a latent factor model for solving the recommender system problem using collaborative filtering. For a recommender system, all the ratings in the rating matrix are bounded within a pre-determined range. In this paper, we propose a new improved matrix factorization approach for such a rating matrix, called Bounded Matrix Factorization (BMF), which imposes a lower and an upper bound on every estimated missing element of the rating matrix. We present an efficient algorithm to solve BMF based on the block coordinate descent method. We show that our algorithm is scalable for large matrices with missing elements on multicore systems with low memory. We present substantial experimental results illustrating that the proposed method outperforms the state of the art algorithms for recommender system such as stochastic gradient descent, alternating least squares with regularization, SVD++ and Bias-SVD on real-world datasets such as Jester, Movielens, Book crossing, Online dating and Netflix.