# Questions tagged [algorithms]

An unambiguous list of computational steps involved in finding a solution to a class of problems.

88 questions
10k views

### Algebra of LDA. Fisher discrimination power of a variable and Linear Discriminant Analysis

Apparently, the Fisher analysis aims at simultaneously maximising the between-class separation, while minimising the within-class dispersion. A useful measure of the discrimination power of a ...
16k views

### Steps done in factor analysis compared to steps done in PCA

I know how to perform PCA (principal component analysis), but I would like to know steps that should be used for factor analysis. To perform PCA, let us consider some matrix $A$, for instance: ...
14k views

### Why PCA of data by means of SVD of the data?

This question is about an efficient way to compute principal components. Many texts on linear PCA advocate using singular-value decomposition of the casewise data. That is, if we have data $\bf X$ ...
3k views

### Canonical Correlation analysis without raw data (algebra of CCA)

I want to run a Canonical Correlation (in R) but I don't have the original (raw) data. I have only the correlation matrix of all the variables. I have seen some ...
12k views

### Efficient online linear regression

I'm analysing some data where I would like to perform ordinary linear regression, however this is not possible as I am dealing with an on-line setting with a continuous stream of input data (which ...
2k views

### Testing random variate generation algorithms

Which methods are used for testing random variate generation algorithms?
26k views

### Period detection of a generic time series

This post is the continuation of another post related to a generic method for outlier detection in time series. Basically, at this point I'm interested in a robust way to discover the periodicity/...
26k views

### What algorithm is used in linear regression?

I usually hear about "ordinary least squares". Is that the most widely used algorithm used for linear regression? Are there reasons to use a different one?
5k views

### Algorithm to dynamically monitor quantiles

I want to estimate the quantile of some data. The data are so huge that they can not be accommodated in the memory. And data are not static, new data keep coming. Does anyone know any algorithm to ...
25k views

### Best PCA algorithm for huge number of features (>10K)?

I previously asked this on StackOverflow, but it seems like it might be more appropriate here, given that it didn't get any answers on SO. It's kind of at the intersection between statistics and ...
18k views

### Generating values from a multivariate Gaussian distribution

I am currently trying to simulate values of a $N$-dimensional random variable $X$ that has a multivariate normal distribution with mean vector $\mu = (\mu_1,...,\mu_N)^T$ and covariance matrix $S$. I ...
6k views

### Is it possible to accumulate a set of statistics that describes a large number of samples such that I can then produce a boxplot?

I must clarify immediately that I am a practicing software developer, not a statistician, and that my college stats class was a very long time ago… That said, I would like to know if there is a ...
17k views

### Optimized implementations of the Random Forest algorithm

I have noticed that there are a few implementations of random forest such as ALGLIB, Waffles and some R packages like randomForest. Can anybody tell me whether ...
21k views

### What is a good algorithm for estimating the median of a huge read-once data set?

I'm looking for a good algorithm (meaning minimal computation, minimal storage requirements) to estimate the median of a data set that is too large to store, such that each value can only be read once ...
4k views

### Data mining: How should I go about finding the functional form?

I'm curious about repeatable procedures that can be used to discover the functional form of the function y = f(A, B, C) + error_term where my only input is a set of ...
8k views

### Pairwise Mahalanobis distances

I need to calculate the sample Mahalanobis distance in R between every pair of observations in a $n \times p$ matrix of covariates. I need a solution that is efficient, i.e. only $n(n-1)/2$ distances ...
673 views

### Algorithm for minimization of sum of squares in regression packages

I'd like to know what technique or techniques are used by regression packages, (in particular the lm function of R) to minimize the sum of squares. Does it use ...
1k views

### Can sub-optimality of various hierarchical clustering methods be assessed or ranked?

Classic agglomerative hierarchical clustering methods are based on a greedy algorithm. This means that they (many of them) are prone to give sub-optimal solutions instead of the global optimum result, ...
36k views

### What is the difference between the forward-backward and Viterbi algorithms?

I want to know what the differences between the forward-backward algorithm and the Viterbi algorithm for inference in hidden Markov models (HMM) are.
14k views

### Measuring entropy/ information/ patterns of a 2d binary matrix

I want to measure the entropy/ information density/ pattern-likeness of a two-dimensional binary matrix. Let me show some pictures for clarification: This display should have a rather high entropy: ...
8k views

### Approximate $e$ using Monte Carlo Simulation

I've been looking at Monte Carlo simulation recently, and have been using it to approximate constants such as $\pi$ (circle inside a rectangle, proportionate area). However, I'm unable to think of a ...
23k views

### How to define the termination condition for gradient descent?

Actually, I wanted to ask you how can I define the terminating condition for gradient descent. Can I stop it based upon the number of iterations, i.e. considering parameter values for, say, 100 ...
6k views

### Do Random Forests exhibit prediction bias?

I think this is a straightforward question, although the reasoning behind why or why not may not be. The reason I ask is that I have recently written my own implementation of a RF and although it ...
14k views

### How should decision tree splits be implemented when predicting continuous variables?

I'm actually writing an implementation of Random Forests but I believe the question is specific to decision trees (independent of RFs). So the context is that I'm creating a node in a decision tree ...
4k views

### How to calculate ratings/rankings from Paired comparison / Pairwise comparison of large data-sets?

As part of my graduate thesis (area: psychology) I have gathered preference data. The data includes approximately 50000 heads-up comparison between elementX and elementX. I have a total of 15 elements....
32k views

### Identify seasonality in time series data [duplicate]

I want to detect presence of seasonality in time series data. I know one can achieve that by plotting the autocorrelation function but I need an automatic process if the series is seasonal or not, ...
4k views

### Online algorithm for mean absolute deviation and large data set

I have a little problem that is making me freaking out. I have to write procedure for an online acquisition process of a multivariate time series. At every time interval (for example 1 second), I get ...
6k views

### LogLikelihood Parameter Estimation for Linear Gaussian Kalman Filter

I have written some code that can do Kalman filtering (using a number of different Kalman-type filters [Information Filter et al.]) for Linear Gaussian State Space Analysis for an n-dimensional state ...
3k views

### Is automated machine learning a dream?

As I discover machine learning I see different interesting techniques such as: automatically tune algorithms with techniques such as grid search, get more ...
8k views

### What fast algorithms exist for computing truncated SVD?

Possibly off topic here, but there exist several (one, two) related questions already. Poking around in the literature (or a google search for Truncated SVD Algorithms) turns up a lot of papers that ...
7k views

### Which optimization algorithm is used in glm function in R?

One can perform a logit regression in R using such code: ...
1k views

### FA: Choosing Rotation matrix, based on “Simple Structure Criteria”

One of the most important issues in using factor analysis is its interpretation. Factor analysis often uses factor rotation to enhance its interpretation. After a satisfactory rotation, the rotated ...
286 views

### Minimisation algorithm for a mix of discreet and continuous parameters?

I have a minimisation problem in which the parameters are a mix of integers and scalars. Some of the integers have a small range, around 0-10 but others range in the thousands. To give some context, ...
2k views

### Is large scale PCA even possible?

Principal component analysis' (PCA) classical way is to do it on an input data matrix which columns have zero mean (then PCA can "maximize variance"). This can be achieved easily by centering the ...
6k views

### How can I (numerically) approximate values for a beta distribution with large alpha & beta

Is there a numerically stable way to calculate values of a beta distribution for large integer alpha, beta (e.g. alpha,beta > 1000000)? Actually, I only need a 99% confidence interval around the mode,...
14k views

### Forcing a set of numbers to a gaussian bell-curve

(This relates to my programming question on Stack Overflow: Bell Curve Gaussian Algorithm (Python and/or C#).) On Answers.com, I found this simple example: Find the arithmetic mean (average) => Sum ...
433 views

### Relatively normalizing values for collaborative filtering

I am trying to derive a formula for my collaborative algorithm problem to calculate popularity rating of an item. I am considering three factors to calculate rating for an item based on three ...
480 views

### Transform sample to achieve target mean, skewness, etc

I have a sample of data with N values from which I calculate basic moments such as mean, standard deviation and skewness. I will then change these moments to different values according to my own rules,...
384 views

### Using Covariance Estimator to Perform Linear Regression?

Suppose you had a method for estimating the population covariance of a vector-valued random variable given observations of that random variable, say $f(Z) \rightarrow C$, where the rows of $Z$ are ...
377 views

### Customization of a standard Bell Curve

Hopefully this isn't a duplicate, I've tried to search for similar things, but to no luck. I'm curious on how you would computationally compute a random distribution of numbers that follows a bell ...
19 views

### Algorithm for creation of groups with cohesion

I don't know if this belongs here, but anyway, here's my doubt. I have a 52x52 matrix with the distances between each pair of 52 points. I want to create an algorithm that classifies them into a ...
17k views

### Difference between standard and spherical k-means algorithms

I would like to understand, what is the major implementation difference between standard and spherical k-means clustering algorithms. In each step, k-means computes distances between element vectors ...
15k views

### Algorithms to compute the running median?

On smaller window sizes, n log n sorting might work. Are there any better algorithms to achieve this?
6k views

### Updating SVD decomposition after adding one new row to the matrix

Suppose that I have a dense matrix $\textbf{A}$ of $m \times n$ size, with SVD decomposition $$\mathbf{A}=\mathbf{USV}^\top.$$ In R I can calculate the SVD as ...
4k views

### How does random forest generate the random forest

I am not an expert of random forest but I clearly understand that the key issue with random forest is the (random) tree generation. Can you explain me how the trees are generated? (i.e. What is the ...
5k views

### What are efficient algorithms to compute singular value decomposition (SVD)?

The Wikipedia article on principal component analysis states that Efficient algorithms exist to calculate the SVD of $X$ without having to form the matrix $X^TX$, so computing the SVD is now the ...
7k views

### Anomaly detection: what algorithm to use?

Context: I'm developing a system that analyzes clinical data to filter out implausible data that might be typos. What I did so far: To quantify the plausibility, my attempt so far was to normalize ...
7k views

### Defining quantiles over a weighted sample

I have a weighted sample, for which I wish to calculate quantiles.1 Ideally, where the weights are equal (whether = 1 or otherwise), the results would be consistent with those of ...