The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [linear-algebra]

The tag has no usage guidance.

174 questions
Filter by
Sorted by
Tagged with
140 views

Comparison of matrix determinant in less than $O(n^2)$

I was reading this question and I think maybe somebody here could help. This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in ...
111 views

Laplace's Approximation for graphical models

A question about Laplace's approximation: In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is ...
34 views

Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
690 views

How to use different size features in SVM?

I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector. ...
Consider these matrices: $A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$ $B=\begin{bmatrix}-1 & -2\\-3 & -4\end{bmatrix}$ Using standard algorithm: $C=\begin{bmatrix}1*-1+2*-3 & 1*... 1answer 27 views Geometric median of two disjoint sets of points lies on line between their respective medians I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets ... 1answer 18 views Avoiding underflow when identifying neighbours of a cell in a grid by using modulo I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, ... 1answer 231 views LP formulation and integer solution existance I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have$m$pieces ... 1answer 263 views maximizing inner product of vectors in an ellipsoid and a given vector I have been wrestling with this for quite a long time but couldn't convince myself that the following is true: What I do understand:$\theta_a$denotes the set of points that are within the ellipsoid.... 1answer 109 views Using random projections for locally sensitive hashing I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents. The proof is such that based on cosine similarity to the vector. In other ... 1answer 84 views Projecting points on a Pareto-front onto a (hyper)plane? I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb. Basically, ... 1answer 617 views Running time of sparse matrix multiplication Given a sparse matrix$M \in \mathbb{R}^{n \times m}$with$n \ll m$and$\mathsf{nnz}$being the number of non-zero-components. What is the running time of computing$M M^T$? 1answer 38 views Using Taylor series in 1D Grayscale Image Could someone point me in the direction of how to solve this? I = [I1, . . . , In] is a 1D grayscale image and D = [D1, . . . , Dn] represents the second derivative of I. I am given the four pixel ... 1answer 146 views Algorithm for projection of polytope Let a convex bounded polytope be given by an intersection of half planes:$Ax \leq b$. Let$z=Cx$be a vector (in my case$z$is 2-dimensional, while$x$has a higher dimension). How can I compute$D$... 1answer 41 views What is the exact definition of a dictionary in the concept of linear algebra and computer science? I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except ... 0answers 53 views How to quickly solve a linear equation for 7000 times? I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ... 0answers 32 views How to make sure matrix completion can generate a matrix with values in expected range? I am doing a matrix completion project. Assume that I have an incomplete matrix like ... 0answers 27 views Equivalent Algorithm with Sharman Morrison inversion I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For$t=1,2,...(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$... 0answers 32 views Randomly choose matrices$A_{j}B = C_{j}$with elements between 0 and 1 Problem I have$J$matrices$C_{j}$, which are$K \times M$. Elements of each matrix$C_{j}$are between 0 and 1. I want to randomly choose$J$matrices$A_{j}$and one matrix$B$such that: ... 1answer 50 views Compute unknown matrices that minimize a sum This problem is about working with smart-phone accelerometers. To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum:$$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|... 0answers 131 views Why solutions for Normal form Ordinary least squares and Linear Regression are different I am trying to apply Linear Regression method for a dataset of 9 sample with around 50 features using python. I have tried different methodology for Linear Regression i.e Closed form OLS(Ordinary ... 0answers 368 views Most stable algorithm to solve a system of linear equations? I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ... 1answer 115 views Solving a graph problem by Gaussian elimination I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule. For a node$x$with adjacent nodes$y_1 , y_2, y_3, y_4,....
I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set \$X\...