Numerous automatic sleep staging approacheshave been proposed to provide an eHealth alternative to thecurrent gold-standard – hypnogram scoring by human experts.However, a majority of such studies exploit data of limited scale,which compromises both the validation and the reproducibilityand transferability of such automatic sleep staging systemsin the real clinical settings. In addition, the computationalissues and physical meaningfulness of the analysis are typicallyneglected, yet affordable computation is a key criterion inBig Data analytics. To this end, we establish a comprehensiveanalysis framework to rigorously evaluate the feasibility ofautomatic sleep staging from multiple perspectives, includingrobustness with respect to the number of training subjects,model complexity, and different classifiers. This is achievedfor a large collection of publicly accessible polysomnography(PSG) data, recorded over 515 subjects. The trade-off betweenaffordable computation and satisfactory accuracy is shown tobe fulfilled by an extreme learning machine (ELM) classifier,which in conjunction with the physically meaningful hiddenMarkov model (HMM) of the transition between the differentsleep stages (smoothing model) is shown to achieve both fastcomputation and highest average Cohen’s kappa value ofκ=0.73(Substantial Agreement). Finally, it is shown thatfor accurate and robust automatic sleep staging, a combinationof structural complexity (multi-scale entropy) and frequency-domain (spectral edge frequency) features is both computation-ally affordable and physically meaningful.